| Information | |
|---|---|
| has gloss | eng: In computer science, 2-satisfiability (abbreviated as 2-SAT or just 2SAT) is the problem of determining whether a collection of two-valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all the constraints. In contrast with 3-satisfiability and with constraint satisfaction problems with more than two values per variable, it has a known polynomial time solution. |
| lexicalization | eng: 2-satisfiability |
| lexicalization | eng: 2-SAT |
| lexicalization | eng: 2SAT |
| instance of | c/NL-complete problems |
| Media | |
|---|---|
| media:img | 2SAT median graph.svg |
| media:img | Implication graph.svg |
Lexvo © 2008-2025 Gerard de Melo. Contact Legal Information / Imprint
