| 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
| |
| dbo:wikiPageLength
|
- 10858 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
