Preuve naturelle
concept en informatique théorique / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Preuve naturelle?
Résumez cet article pour un enfant de 10 ans
AFFICHER TOUTES LES QUESTIONS
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.