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.

• Singly Even Number
• Singular Homology
• Singularity
• Singular Point (Algebraic Curve)
• Singular Point (Differential Equation)
• Singular Point (Function)
• Singular Series
• Singular System
• Singular Value
• Singular Value Decomposition
• Sinh
• Sink (Directed Graph)
• Sink (Map)
• Sinusoidal Projection
• Sinusoidal Spiral
• Sinusoidal Spiral Inverse Curve
• Sinusoidal Spiral Pedal Curve
• Sister Celine's Method
• Site Percolation
• Siteswap
• Six-Color Theorem
• Skein Relationship
• Skeleton
• Skeleton Division
• Skew Conic