| dbo:abstract
|
- In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then and therefore That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial hierarchy at its second level. Such a collapse is believed unlikely, so the theorem is generally viewed by complexity theorists as evidence for the nonexistence of polynomial size circuits for SAT or for other NP-complete problems. A proof that such circuits do not exist would imply that P ≠ NP. As P/poly contains all problems solvable in randomized polynomial time (Adleman's theorem), the theorem is also evidence that the use of randomization does not lead to polynomial time algorithms for NP-complete problems. The Karp–Lipton theorem is named after Richard M. Karp and Richard J. Lipton, who first proved it in 1980. (Their original proof collapsed PH to , but Michael Sipser improved it to .) Variants of the theorem state that, under the same assumption, MA = AM, and PH collapses to SP2 complexity class. There are stronger conclusions possible if PSPACE, or some other complexity classes are assumed to have polynomial-sized circuits; see P/poly. If NP is assumed to be a subset of BPP (which is a subset of P/poly), then the polynomial hierarchy collapses to BPP. If coNP is assumed to be subset of NP/poly, then the polynomial hierarchy collapses to its third level. (en)
- En théorie de la complexité, le théorème de Karp–Lipton affirme que si le problème de satisfiabilité booléenne (SAT) est résolu par une famille de circuits booléens avec un nombre polynomial de portes logiques (en la taille de la formule propositionnelle à tester), alors la hiérarchie polynomiale s’effondre au second niveau. Plus formellement, si alors (et donc ) où NP est la classe des problèmes en temps polynomial non déterministe, P/poly est la classe de complexité de temps polynomial non uniforme, et et sont les classes du second niveau de la hiérarchie polynomiale. Le théorème de Karp–Lipton tire son nom de Richard Karp et Richard J. Lipton, qui ont été les premiers à le prouver, en 1980. La preuve originale montrait l’effondrement de PH à , mais Michael Sipser l’a améliorée pour atteindre . (fr)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13621 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:b
| |
| dbp:p
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then and therefore That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial hierarchy at its second level. Such a collapse is believed unlikely, so the theorem is generally viewed by complexity theorists as evidence for the nonexistence of polynomial size circuits for SAT or for other NP-complete problems. A proof that such circuits do not exist would imply that P ≠ NP. As P/poly contains all problems solvable in randomized polynomial time (Adleman's t (en)
- En théorie de la complexité, le théorème de Karp–Lipton affirme que si le problème de satisfiabilité booléenne (SAT) est résolu par une famille de circuits booléens avec un nombre polynomial de portes logiques (en la taille de la formule propositionnelle à tester), alors la hiérarchie polynomiale s’effondre au second niveau. Plus formellement, si alors (et donc ) (fr)
|
| rdfs:label
|
- Théorème de Karp-Lipton (fr)
- Karp–Lipton theorem (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
