Information About2-satisfiability |
| CATEGORIES ABOUT 2-SATISFIABILITY | |
| computational complexity theory | |
| nl-complete problems | |
| satisfiability problems | |
|
: where means OR, means AND, each x is a variable, with or without a NOT in front of it, and each variable can appear multiple times in the expression. Unlike general Satisfiability or 3-satisfiability which are NP-complete and have no known efficient Algorithm , 2-satisfiability can be solved in Polynomial Time . There are several known polynomial time algorithms for 2-SAT, for example, based on Resolution or Random Walk s. More powerfully, 2-satisfiability is NL-complete (Papadimitriou 1994, Thrm. 16.3), meaning that it is one of the "hardest" or "most expressive" problems which can be solved in nondeterministic logspace ( NL ). A related problem is maximum-2-satisfiability (MAX-2-SAT) in which the input is still a 2-CNF but we have to determine the maximum number of clauses that can be simultaneously satisfied by an assignment. MAX-2-SAT is a particular case of Maximum-satisfiability . It is NP-complete . REFERENCES
|
|
|