Théorème de Karp-Lipton

Cet article fait référence à un vocabulaire spécialisé. Pour plus d'informations, voir : hiérarchie polynomiale.

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

NP\subseteq P/poly

alors

\Pi _{2}=\Sigma _{2}\,

(et donc

\mathrm {PH} =\Sigma _{2}

)

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 $\Sigma _{2}$ et $\Pi _{2}$ 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 à $\Sigma _{3}$ , mais Michael Sipser l’a améliorée pour atteindre $\Sigma _{2}$ .

Un tel effondrement est considéré comme peu probable ; ce théorème est donc considéré par la plupart des théoriciens^[Qui ?] de la complexité comme un argument en faveur de la non-existence de circuits de taille polynomiale pour SAT et les autres problèmes NP-complets. Une preuve que de tels circuits n’existent pas impliquerait que P ≠ NP. Comme P/poly contient tous les problèmes solvables en temps polynomial randomisé d'après le théorème d’Adleman, le théorème de Karp–Lipton est aussi un argument pour affirmer que l’utilisation d’aléatoire ne conduit pas à avoir des algorithmes en temps polynomial pour les problèmes NP-complets.

Des variantes du théorème affirment que, sous la même hypothèse, MA = AM, et PH s’effondre au niveau de la classe $S_{2}^{P}$ . Il y a des conclusions plus fortes possibles si on suppose que PSPACE, ou d’autres classes classes de complexité, ont des circuits de taille polynomiale (voir P/poly).

Si NP est supposé être une sous-classe de BPP (qui est elle-même une sous-classe de P/poly), alors la hiérarchie polynomiale s’effondre au niveau de BPP^[1].

Si coNP est supposée être une sous-classe de NP/poly, alors la hiérarchie polynomiale s’effondre à son troisième niveau.

Intuition

Supposons que non seulement des circuits de taille polynomiale pour SAT existent, mais en plus qu’ils peuvent être construits par un algorithme en temps polynomial. Alors, SAT lui-même peut être résolu par un algorithme polynomial qui construit le circuit et ensuite l’applique. Ainsi, des circuits constructibles efficacement pour SAT impliquent un effondrement plus fort, P = NP.

L’hypothèse du théorème de Karp–Lipton, que ces circuits existent, est plus faible. Mais il est toujours possible pour un algorithme de la classe de complexité $\Sigma _{2}$ de deviner un circuit correct pour SAT. La classe de complexité $\Sigma _{2}$ décrit des problèmes de la forme $\exists x\forall y\;\psi (x,y)$ où $\psi$ est n’importe quel prédicat calculable en temps polynomial. La puissance existentielle du premier quantificateur peut être utilisée pour deviner un circuit correct pour SAT, et la puissance universelle du second pour vérifier que le circuit est correct. Une fois que ce circuit est deviné et vérifié, l’algorithme de la classe $\Sigma _{2}$ peut s’en servir comme sous-routine pour résoudre d’autres problèmes.

Auto-réductibilité

Pour comprendre mieux la preuve du théorème de Karp–Lipton, on considère le problème de tester si un circuit $c$ est un circuit correct pour les instances de SAT d’une taille donnée, et on montre que le problème de tester ce circuit appartient à $\Pi _{1}$ . Ainsi, il existe un prédicat $V$ calculable en temps polynomial tel que $c$ est un circuit correct si et seulement si, pour tout $z$ de taille bornée par un polynôme, $V(c,z)$ est vrai.

Le circuit $c$ est un circuit correct pour SAT s’il satisfie deux propriétés :

Pour chaque paire $(s,x)$ où $s$ est une instance de SAT et $x$ une solution à cette instance, $c(s)$ est vrai
Pour chaque instance $s$ de SAT pour laquelle $c(s)$ est vraie, $s$ doit être résoluble.

La première de ces propriétés est déjà sous la forme d’un problème de la classe $\Pi _{1}$ . Pour vérifier la seconde propriété, on doit utiliser la propriété d’auto-réductibilité de SAT.

L’auto-réductibilité décrit le fait que, si on peut tester rapidement si une instance de SAT est résoluble, alors on peut trouver presque aussi vite une solution explicite à cette instance. Pour trouver une solution à l’instance $s$ , on choisit une variable booléenne $x$ qui est une entrée de $s$ et on construit deux instances plus petites $s_{0}$ et $s_{1}$ où $s_{i}$ correspond à la formule obtenue en remplaçant $x$ par la constante $i$ . Une fois que ces deux plus petites instances ont été construites, on applique le test de solvabilité à chacune d’elles. Si l’un de ces tests renvoie qu’une de ces petites instances est satisfiable, on continue à résoudre cette instance jusqu’à ce qu’une solution complète en soit déduite.

Pour utiliser l’auto-réductibilité pour vérifier la seconde propriété d’un circuit correct pour SAT, on la réécrit ainsi :

Pour chaque instance $s$ de SAT pour laquelle $c(s)$ est vrai, la procédure d’auto-réduction décrite ci-dessus trouve une solution valide à $s$ .

Ainsi, on peut tester dans $\Pi _{1}$ si $c$ est un circuit valide pour résoudre SAT.

Théorème de Karp-Lipton

Intuition

Auto-réductibilité

AM = MA

Références

Related Articles