The 2SAT Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 9: | Line 9: | ||
=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>). | 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. | ||
Revision as of 04:19, 30 November 2021
External
- 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
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 2 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.