Schaefer's dichotomy theorem (original) (raw)
In computational complexity theory, a branch of computer science, Schaefer's dichotomy theorem states necessary and sufficient conditions under which a finite set S of relations over the Boolean domain yields polynomial-time or NP-complete problems when the relations of S are used to constrain some of the propositional variables.It is called a dichotomy theorem because the complexity of the problem defined by S is either in P or NP-complete as opposed to one of the classes of intermediate complexity that is known to exist (assuming P ≠ NP) by Ladner's theorem.
| Property | Value |
|---|---|
| dbo:abstract | In computational complexity theory, a branch of computer science, Schaefer's dichotomy theorem states necessary and sufficient conditions under which a finite set S of relations over the Boolean domain yields polynomial-time or NP-complete problems when the relations of S are used to constrain some of the propositional variables.It is called a dichotomy theorem because the complexity of the problem defined by S is either in P or NP-complete as opposed to one of the classes of intermediate complexity that is known to exist (assuming P ≠ NP) by Ladner's theorem. Special cases of Schaefer's dichotomy theorem include the NP-completeness of SAT (the Boolean satisfiability problem) and its two popular variants 1-in-3 SAT and not-all-equal 3SAT (often denoted by NAE-3SAT). In fact, for these two variants of SAT, Schaefer's dichotomy theorem shows that their monotone versions (where negations of variables are not allowed) are also NP-complete. (en) Em teoria da complexidade computacional, um ramo da Ciência da Computação, o teorema da dicotomia de Schaefer estabelece as condições necessárias e suficientes sob as quais um conjunto finito S de relações sobre o domínio Booleano produza problemas de tempo polinomial ouNP-completo quando as relações de S são usadas para restringir algumas das variáveis proposicionais. É chamado de teorema da dicotomia porque a complexidade do problema definido por S será P ou NP-completo em oposição a alguma das classes de complexidade NP-Intermediário que é sabida existir (assumindo P ≠ NP) pelo teorema de . Casos especias do teorema da dicotomia de Schaefer incluem a NP-completude de SAT (o problema da satisfatibilidade Booleana) e suas duas variantes populares 1-in-3 SAT e NAE-3SAT (Not-All-Equal 3SAT). Na verdade, para estas duas variantes de SAT, o teorema da dicotomia de Schaefer nos mostra suas versões monótonas (onde as negações das variáveis não são permitidas) também são NP-completas. (pt) |
| dbo:wikiPageID | 4638322 (xsd:integer) |
| dbo:wikiPageLength | 10858 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1106157370 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Decision_problem dbr:Universal_algebra dbr:Not-all-equal_3-satisfiability dbr:One-in-three_3SAT dbr:Galois_connection dbr:NP-complete dbr:Constraint_satisfaction_problem dbr:L_(complexity) dbc:Theorems_in_computational_complexity_theory dbr:Computational_complexity_theory dbr:Computer_science dbr:Horn_clause dbr:P_(complexity) dbr:Max/min_CSP/Ones_classification_theorems dbr:P-complete dbr:Reduction_(complexity) dbc:Constraint_programming dbr:Boolean_domain dbr:Boolean_satisfiability_problem dbr:Propositional_variable dbr:NP-intermediate dbr:Sharp-P-complete dbr:NL-complete dbr:P_versus_NP_problem dbr:Ladner's_theorem |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Theorems_in_computational_complexity_theory dbc:Constraint_programming |
| rdf:type | yago:WikicatTheoremsInComputationalComplexityTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | In computational complexity theory, a branch of computer science, Schaefer's dichotomy theorem states necessary and sufficient conditions under which a finite set S of relations over the Boolean domain yields polynomial-time or NP-complete problems when the relations of S are used to constrain some of the propositional variables.It is called a dichotomy theorem because the complexity of the problem defined by S is either in P or NP-complete as opposed to one of the classes of intermediate complexity that is known to exist (assuming P ≠ NP) by Ladner's theorem. (en) Em teoria da complexidade computacional, um ramo da Ciência da Computação, o teorema da dicotomia de Schaefer estabelece as condições necessárias e suficientes sob as quais um conjunto finito S de relações sobre o domínio Booleano produza problemas de tempo polinomial ouNP-completo quando as relações de S são usadas para restringir algumas das variáveis proposicionais. (pt) |
| rdfs:label | Schaefer's dichotomy theorem (en) Teorema da Dicotomia de Schaefer (pt) |
| owl:sameAs | freebase:Schaefer's dichotomy theorem yago-res:Schaefer's dichotomy theorem wikidata:Schaefer's dichotomy theorem dbpedia-pt:Schaefer's dichotomy theorem https://global.dbpedia.org/id/4utGJ |
| prov:wasDerivedFrom | wikipedia-en:Schaefer's_dichotomy_theorem?oldid=1106157370&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Schaefer's_dichotomy_theorem |
| is dbo:knownFor of | dbr:Thomas_Jerome_Schaefer |
| is dbo:wikiPageWikiLink of | dbr:Not-all-equal_3-satisfiability dbr:Constraint_satisfaction_problem dbr:Complexity_of_constraint_satisfaction dbr:Max/min_CSP/Ones_classification_theorems dbr:Boolean_satisfiability_problem dbr:List_of_theorems dbr:Thomas_Jerome_Schaefer dbr:NP-intermediate dbr:Schaefer's_theorem |
| is dbp:knownFor of | dbr:Thomas_Jerome_Schaefer |
| is foaf:primaryTopic of | wikipedia-en:Schaefer's_dichotomy_theorem |