✳flâneur — a map of the web's best reading

Planar SAT

en.wikipedia.org · 2,621 words · saved by 1 readers

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.

Planar SAT - Wikipedia Jump to content From Wikipedia, the free encyclopedia Boolean satisfiability problem restricted to a planar incidence graph This article has multiple issues. Please help improve it or discuss these issues on the talk page . ( Learn how and when to remove these messages ) This article provides insufficient context for those unfamiliar with the subject . Please help improve the article by providing more context for the reader . ( April 2019 ) ( Learn how and when to remove this message ) This article may be too technical for most readers to understand . Please help improve

Explore this link on the map →

related reading