Planar SAT (original) (raw)
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
Property | Value |
---|---|
dbo:abstract | 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. (en) |
dbo:thumbnail | wiki-commons:Special:FilePath/Planar_SAT_example.png?width=300 |
dbo:wikiPageID | 60623303 (xsd:integer) |
dbo:wikiPageLength | 15606 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1115363784 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:NP_(complexity) dbc:Electronic_design_automation dbr:Cycle_(graph_theory) dbr:Validity_(logic) dbr:Shakashaka dbr:Nurikabe_(puzzle) dbr:1-in-3-SAT dbc:NP-complete_problems dbr:Maximum_cut dbr:NP-complete dbr:Contradiction dbr:Computer_science dbr:Plane_(geometry) dbr:Minimum-weight_triangulation dbr:Dynamic_programming dbr:Edge_coloring dbr:Graph_embedding dbr:Rectilinear_polygon dbr:Reduction_(complexity) dbc:Boolean_algebra dbc:Satisfiability_problems dbr:Bipartite_graph dbr:Triangulation_(geometry) dbr:Directed_acyclic_graph dbr:3SAT dbr:Boolean_satisfiability_problem dbr:Planar_graph dbr:Circuit_satisfiability_problem dbr:Fillomino dbr:If_and_only_if dbr:Satisfiability dbr:NP-hardness dbr:Polygon_partition dbr:Tatamibari dbr:Tentai_Show dbr:Boolean_logic dbr:Incidence_graph dbr:Formula_(mathematical_logic) dbr:Strongly_NP-hard dbr:File:Planar_SAT_Crossover_Gadget.png dbr:File:Planar_SAT_example.png |
dbp:wikiPageUsesTemplate | dbt:Multiple_issues dbt:Reflist dbt:Technical dbt:Context |
dct:subject | dbc:Electronic_design_automation dbc:NP-complete_problems dbc:Boolean_algebra dbc:Satisfiability_problems |
rdfs:comment | 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 (en) |
rdfs:label | Planar SAT (en) |
owl:sameAs | wikidata:Planar SAT https://global.dbpedia.org/id/Bv1S8 |
prov:wasDerivedFrom | wikipedia-en:Planar_SAT?oldid=1115363784&ns=0 |
foaf:depiction | wiki-commons:Special:FilePath/Planar_SAT_Crossover_Gadget.png wiki-commons:Special:FilePath/Planar_SAT_example.png |
foaf:isPrimaryTopicOf | wikipedia-en:Planar_SAT |
is dbo:wikiPageWikiLink of | dbr:Boolean_satisfiability_problem dbr:Polygon_partition dbr:True_quantified_Boolean_formula dbr:Tentai_Show |
is foaf:primaryTopic of | wikipedia-en:Planar_SAT |