NP-completeness and difficulty of all possible solutions

93 Views Asked by At

Take the SAT problem (or any other NP-complete).

Is the set of all possible combinations of SAT problems are NP-complete?

Or maybe there are combinations that can be quickly solved?

If I take a random logical formula of n variables is always always be NP-complete problem? There are no exceptions for any particular forms of formulas?

1

There are 1 best solutions below

1
On BEST ANSWER

Not all subsets of SAT are NP-complete. Schaefer's dichotomy theorem identifies infinite subsets of SAT that are in P, with the remainder being NP-complete. The known subsets that are in P are 2-SAT, HORN-SAT, ANTIHORN-SAT, XOR-SAT and SAT instances that can be satisfied with all-true or all-false assignments.