The 2SAT Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
=External=
=External=
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/ERxmM/the-2-sat-problem
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/ERxmM/the-2-sat-problem
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/kRmJe/random-walks-on-a-line
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/YltoR/analysis-of-papadimitrious-algorithm


=Internal=
=Internal=
Line 10: Line 8:
=Overview=
=Overview=
=The Problem=
=The Problem=
Given a set of n boolean variables x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>, that can be set to <code>true</code> or <code>false</code> and a set of m clauses of 2 literals each (a "literal" is a variable or the negation of the variable: x<sub>i</sub> or !x<sub>i</sub>). The output is determining whether there is a variable assignment that simultaneously satisfies every clause.  
Given a set of ''n'' boolean variables x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>, that can be set to <code>true</code> or <code>false</code> and a set of ''m'' clauses of two literals each (a "literal" is a variable or the negation of the variable: x<sub>i</sub> or !x<sub>i</sub>). The output is determining whether there is a variable assignment that simultaneously satisfies every clause.  


The 2SAT problem can be solved in polynomial time - it is not an NP-complete problem.
The 2SAT problem can be solved in polynomial time - it is not an NP-complete problem. Unlike 2SAT, the 3SAT problem is [[NP_Completeness|NP-complete]].


=Algorithms=
=Algorithms=

Latest revision as of 04:58, 30 November 2021

External

Internal

Overview

The Problem

Given a set of n boolean variables x1, x2, ..., xn, that can be set to true or false and a set of m clauses of two literals each (a "literal" is a variable or the negation of the variable: xi or !xi). The output is determining whether there is a variable assignment that simultaneously satisfies every clause.

The 2SAT problem can be solved in polynomial time - it is not an NP-complete problem. Unlike 2SAT, the 3SAT problem is NP-complete.

Algorithms