NP-completeness and difficulty of all possible solutions

Question

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?

Kyle Jones · Accepted Answer · 2016-12-24T01:18:45.593

1

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.

edited Dec 24 '16 at 01:18

answered Dec 18 '16 at 05:26

Kyle Jones

1,871

Also, SAT for some non-clausal representations like DNF and BDDs is in P. – Fabio Somenzi Dec 18 '16 at 06:39

NP-completeness and difficulty of all possible solutions

1 Answers1