On the gap between the complexity of SAT and minimization for certain classes of boolean formulas

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10285647" target="_blank" >RIV/00216208:11320/14:10285647 - isvavai.cz</a>
Result on the web
<a href="http://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Boolean_Cepek_Gursky.pdf" target="_blank" >http://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Boolean_Cepek_Gursky.pdf</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On the gap between the complexity of SAT and minimization for certain classes of boolean formulas
Original language description
It is a wellknown fact that the satisfiability problem (SAT) for Boolean formulas in a conjunctive normal form (CNF) is NP complete, i.e. 1 complete. It is also known that the decision version of Boolean minimization for CNF inputs is 2 complete. On theother hand there are several subclasses of CNFs (e.g. Horn CNFs) for which SAT is known to be in P = 0 while the minimization problem is 1 complete. Thus, for both the general case and the above mentioned subclasses the gap between the complexity of SATand minimization is exactly one level in the polynomial hierarchy. There are also some subclasses (e.g. quadratic CNFs) for which there is no gap because both SAT and minimization are in P = 0. In this short note we shall systematically study different classes of Boolean functions with respect to the size of the mentioned gap and show that there also exist classes for which the gap between the complexity of SAT and minimization is the maximum possible (two levels in the polynomial hierar
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)