SAT for pedestrians

2014/08/13 by Bernd Schuh, Schuh, Bernd R.
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Management and Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.1408.3286

openalex publication_date 2014/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The aim of this short note is mainly pedagogical. It summarizes some knowledge about Boolean satisfiability (SAT) and the P=NP? problem in an elementary mathematical language. A convenient scheme to visualize and manipulate CNF formulae is introduced. Also some results like the formulae for the number of unsatisfied clauses and the number of solutions might be unknown.

Related

• A novel approach of solving the CNF-SAT problem
• A Critique of Kumar's "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications on P versus NP problem."
• Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and its Implications on P versus NP problem
• A New Approach to CNF-SAT From a Probabilistic Point of View
• An Improved Upper Bound for SAT