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

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

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

Popis výsledku anglicky

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

Druh

O - Ostatní výsledky

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

Kód důvěrnosti údajů

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