Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
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
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 C1 & ... & Cm, where each clause Ci has the form a \/ b or a \/ b \/ c, with no more than three literals -- i.e., propositional variables vi or their negations ~v …