Physical Sciences and Mathematics Commons^™

A Natural Feasible Algorithm That Checks Satisfiability Of 2-Cnf Formulas And, If The Formulas Is Satisfiable, Finds A Satisfying Vector, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main results in Theory of Computation courses is the proof that propositional satisfiability is NP-complete. This means that, unless P = NP (which most computer scientists believe to be impossible), no feasible algorithm is possible for solving propositional satisfiability problems. This result is usually proved on the example of 3-CNF formulas, i.e., formulas of the type C₁ & ... & C_m, where each clause C_i has the form a \/ b or a \/ b \/ c, with no more than three literals -- i.e., propositional variables v_i or their negations ~v …