Planar SAT (original) (raw)

About DBpedia

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

thumbnail

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