Abstrakt
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 the other 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 SAT and 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 hierarchy). To this end we shall recall a recent result showing that the minimization of the so called matched CNFs is 2 complete.