Preuve naturelle

La théorie de la complexité consiste notamment à classer les problèmes algorithmiques selon leurs difficultés. Les définitions classiques des classes de complexité, par exemple celles des classes P et NP, considèrent les ressources nécessaires pour résoudre le problème sur une machine de Turing. Cependant pour montrer des bornes inférieures, il est souvent plus aisé de considérer un autre modèle de calcul (en), les circuits booléens. Par exemple, pour prouver que P est différent de NP, une stratégie classique est de montrer que P/poly, un analogue en circuit de P, ne contient pas tous les problèmes de NP[1].

Les preuves naturelles sont un type de preuve de borne inférieures pour les circuits booléens. Ces preuves suivent la stratégie suivante : exhiber une propriété d'un certain problème tel qu'aucun circuit de la classe considérée ne la satisfait.

Étant donnée une classe de circuit U, une propriété qui n'est pas satisfaite par U est une suite ${\displaystyle (C_{n})}$ de fonctions booléennes, telle que si une suite ${\displaystyle f_{n}}$ appartient à ${\displaystyle C_{n}}$ pour une infinité de n, alors ${\displaystyle (f_{n})_{n}}$ n'appartient pas à U.

On peut considérer les ${\displaystyle C_{n}}$ elles-mêmes comme un langage, en les décrivant par leurs tables de vérité[1]. On dit que ${\displaystyle C_{n}}$ est ${\displaystyle \Gamma }$-calculable, si le problème de reconnaître ces tables de vérité est dans une classe de complexité ${\displaystyle \Gamma }$.

D'autre part, on dit que beaucoup de fonctions satisfont une propriété si une proportion supérieure à ${\displaystyle 2^{-O(n)}}$ d'entre elles l'ont.

Enfin une propriété est dite ${\displaystyle \Gamma }$-naturelle si elle est ${\displaystyle \Gamma }$-calculable et si beaucoup de fonctions la satisfont[2]. Dans le contexte de P et NP, on dit que ${\displaystyle C_{n}}$ est calculable efficacement si le langage est dans P/poly, et on parle simplement de propriété naturelle pour les propriétés P/poly-naturelles.

Les preuves naturelles sont celles qui exhibent des propriétés naturelles.

Les preuves qui démontrent que la fonction parité n'est pas dans la classe AC⁰ sont des preuves AC⁰-naturelles[2].

Le théorème principal de Razborov et Rudich est le suivant :

S'il existe une propriété naturelle ${\displaystyle C_{n}}$ qui n'est satisfaite pour aucune fonction de P/poly, alors il n'existe pas de famille de générateurs pseudo-aléatoires ${\displaystyle 2^{n^{\epsilon }}}$-difficiles.

On peut aussi exprimer l'hypothèse par des fonctions à sens unique : si des fonctions de difficulté sous-exponentielle existent, alors il n'existe pas de preuves naturelles[3].

De façon générale, le théorème dit que l'on est dans l'une des situations suivantes :

• ou bien il n'y a pas de générateurs pseudo-aléatoire ${\displaystyle 2^{n^{\epsilon }}}$-difficiles, ce qui est considéré comme improbable,
• ou bien P=NP, ce qui n'est pas l'avis majoritaire non plus,
• ou bien P est différent de NP, mais les techniques de preuve classiques ne fonctionnent pas[4].

Alexander Razborov et Steven Rudich ont obtenu le prix Gödel pour leur article[2] sur les preuves naturelles[5].

• Portail de l'informatique théorique