Satisfiability Problem

Deciding whether a given Boolean formula in conjunctive normal form has an assignment that makes the formula``true.'' In 1971, Cook showed that the problem is NP-Complete.

References

Cook, S. A. and Mitchell, D. G. ``Finding Hard Instances of the Satisfiability Problem: A Survey.'' In Satisfiability problem: theory and applications (Piscataway, NJ, 1996). Theoret. Comput. Sci., Vol. 35. Providence, RI: Amer. Math. Soc., pp. 1-17, 1997.

• Quartic Reciprocity Theorem
• Quartic Surface
• Quartile
• Quartile Deviation
• Quartile Range
• Quartile Skewness Coefficient
• Quartile Variation Coefficient
• Quasiamicable Pair
• Quasiconformal Map
• Quasigroup
• Quasiperfect Number
• Quasiperiodic Function
• Quasiperiodic Motion
• Quasirandom Sequence
• Quasiregular Polyhedron
• Quasirhombicosidodecahedron
• Quasirhombicuboctahedron
• Quasisimple Group
• Quasithin Theorem
• Quasitruncated Cuboctahedron
• Quasitruncated Dodecadocahedron
• Quasitruncated Dodecahedron
• Quasitruncated Great Stellated Dodecahedron
• Quasitruncated Hexahedron
• Quasitruncated Small Stellated Dodecahedron