| Property |
Value |
| dbo:abstract
|
- 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)
- 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
|
- 6462 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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
|
- Karp–Lipton theorem (en)
- Théorème de Karp-Lipton (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
