Planar SAT
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, the planar 3-satisfiability problem (abbreviated PLANAR 3SAT or PL3SAT) is an extension of the classical Boolean 3-satisfiability problem to a planar incidence graph. In other words, it asks whether the variables of a given Boolean formula—whose incidence graph consisting of variables and clauses can be embedded on a plane—can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable. Like 3SAT, PLANAR-SAT is NP-complete, and is commonly used in reductions.
In computer science, the planar 3-satisfiability problem (abbreviated PLANAR 3SAT or PL3SAT) is an extension of the classical Boolean 3-satisfiability problem to a planar incidence graph. In other words, it asks whether the variables of a given Boolean formula—whose incidence graph consisting of variables and clauses can be embedded on a plane—can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable. Like 3SAT, PLANAR-SAT is NP-complete, and is commonly used in reductions. \begin{array}{ll} (\lnot a_2 \lor \lnot b_2 \lor \alpha) \land (a_2 \lor \lnot \alpha) \land (b_2 \lor \lnot \alpha), &\quad \text{i.e.,} \quad a_2 \land b_2 \leftrightarrow \alpha \\ (\lnot a_2 \lor b_1 \lor \beta) \land (a_2 \lor \lnot \beta) \land (\lnot b_1 \lor \lnot \beta), &\quad \text{i.e.,} \quad a_2 \land \lnot b_1 \leftrightarrow \beta \\ (a_1 \lor b_1 \lor \gamma) \land (\lnot a_1 \lor \lnot \gamma) \land (\lnot b_1 \lor \lnot \gamma), &\quad \text{i.e.,} \quad \lnot a_1 \land \lnot b_1 \leftrightarrow \gamma \\ (a_1 \lor \lnot b_2 \lor \delta) \land (\lnot a_1 \lor \lnot \delta) \land (b_2 \lor \lnot \delta), &\quad \text{i.e.,} \quad \lnot a_1 \land b_2 \leftrightarrow \delta \\ (\alpha \lor \beta \lor \xi) \land (\gamma \lor \delta \lor \lnot \xi), &\quad \text{i.e.,} \quad \alpha \lor \beta \lor \gamma \lor \delta \\ (\lnot\alpha \lor \lnot\beta) \land (\lnot\beta \lor \lnot\gamma) \land (\lnot\gamma \lor \lnot\delta) \land (\lnot\delta \lor \lnot\alpha), &\\ (a_2 \lor \lnot a) \land (a \lor \lnot a_2) \land (b_2 \lor \lnot b) \land (b \lor \lnot b_2), &\quad \text{i.e.,} \quad a \leftrightarrow a_2, ~ b \leftrightarrow b_2 \\ \end{array} If the edge (a, c 1 ) is inverted in the original graph, (a 1 , c 1 ) should be inverted in the crossover gadget. Similarly if the edge (b, c 2 ) is inverted in the original, (b 1 , c 2 ) should be inverted. One can easily show that these clauses are satisfiable if and only if a \leftrightarrow a_1 and b \leftrightarrow b_1 . This algorithm shows that it is possible to convert each crossing into its planar equivalent using only a constant amount of new additions. Since the number of crossings is polynomial in terms of the number of clauses and variables, the reduction is polynomial.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1351698472 under CC BY-SA 4.0; modifications have been made.