text size
Výsledky projektu Vlastnosti booleovských formulí a jejich souvislost s konstrukcí SAT-solverů
Výsledky
  Typ výsledku
Autor celku
Název celku(Celkem 4 zázn.)
|
|---|
| Čepek, Ondřej; Gurský Štefan; Kučera Petr. On Minimum Representations of Matched Formulas. Journal of Artificial Intelligence Research, 2014, sv. 51, s. 707–723. ISSN 1076-9757. IF 0.904. [] Článok sa zaoberá triedou formulí nazývanou matched. Táto trieda je zaujímavá tým, že je pre ňu problém splniteľnosti triviálny, ale problém minimalizácie zostáva \Sigma_2 úplný. V článku ponúkame nový výrazne zjednodušený dôkaz tohto faktu a skúmame štruktúru matched formúl. Hlavným výsledkom článku je poznatok, že pokiaľ Booleovská funkcia má nejakú matched reprezentáciu, tak každá jej najmenšia reprezentácia (do počtu klauzúl) musí byť matched. |
| Babka Martin, Balyo Tomáš, Čepek Ondřej, Gurský Štefan, Kučera Petr, Vlček Václav. Complexity issues related to propagation completeness. Artificial Intelligence, 2013, sv. 203, s. 19–34. ISSN 0004-3702. IF 2.194. [] |
| Čepek, Ondřej; Gurský Štefan, Čepek, Ondřej; Gurský Štefan. Tractability conditions for classes of CNFs and their influence on the complexity of CNF minimization. 17th Czech-Japan Seminar on Data Analysis & Decision Making. 2014 [] |
| Čepek, Ondřej; Gurský Štefan, Čepek, Ondřej; Gurský Štefan. On the Gap between the Complexity of SAT and Minimization for Certain Classes of Boolean Formulas. International Symposium on Artificial Intelligence and Mathematics 2014. [] |