Preuve naturelle

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.

Contexte

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, 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.

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.

Définitions

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

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

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

Enfin une propriété est dite $\Gamma$-naturelle si elle est $\Gamma$-calculable et si beaucoup de fonctions la satisfont. Dans le contexte de P et NP, on dit que $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.

Exemples

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

Résultat de Razborov et Rudich sur P et NP

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

S'il existe une propriété naturelle $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 $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.

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 $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.

Histoire

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