The 2SAT Problem

From NovaOrdis Knowledge Base
Revision as of 04:58, 30 November 2021 by Ovidiu (talk | contribs) (→‎External)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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