| Property |
Value |
| dbo:abstract
|
- En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP. (fr)
- En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP. (fr)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5425 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:fr
|
- modèle de calcul (fr)
- modèle de calcul (fr)
|
| prop-fr:langue
| |
| prop-fr:trad
|
- computational model (fr)
- computational model (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP. (fr)
- En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP. (fr)
|
| rdfs:label
|
- Natural proof (en)
- Preuve naturelle (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
