Théorème de Karp-Lipton

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 ${\displaystyle NP\subseteq P/poly}$ alors ${\displaystyle \Pi _{2}=\Sigma _{2}\,}$ (et donc ${\displaystyle \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 ${\displaystyle \Sigma _{2}}$ et ${\displaystyle \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 à ${\displaystyle \Sigma _{3}}$, mais Michael Sipser l’a améliorée pour atteindre ${\displaystyle \Sigma _{2}}$.

Discussion[modifier | modifier le code]

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 ${\displaystyle 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[modifier | modifier le code]

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é ${\displaystyle \Sigma _{2}}$ de deviner un circuit correct pour SAT. La classe de complexité ${\displaystyle \Sigma _{2}}$ décrit des problèmes de la forme ${\displaystyle \exists x\forall y\;\psi (x,y)}$ où ${\displaystyle \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 ${\displaystyle \Sigma _{2}}$ peut s’en servir comme sous-routine pour résoudre d’autres problèmes.

Auto-réductibilité[modifier | modifier le code]

Pour comprendre mieux la preuve du théorème de Karp–Lipton, on considère le problème de tester si un circuit ${\displaystyle 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 à ${\displaystyle \Pi _{1}}$. Ainsi, il existe un prédicat ${\displaystyle V}$ calculable en temps polynomial tel que ${\displaystyle c}$ est un circuit correct si et seulement si, pour tout ${\displaystyle z}$ de taille bornée par un polynôme, ${\displaystyle V(c,z)}$ est vrai.

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

• Pour chaque paire ${\displaystyle (s,x)}$ où ${\displaystyle s}$ est une instance de SAT et ${\displaystyle x}$ une solution à cette instance, ${\displaystyle c(s)}$ est vrai
• Pour chaque instance ${\displaystyle s}$ de SAT pour laquelle ${\displaystyle c(s)}$ est vraie, ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle s}$, on choisit une variable booléenne ${\displaystyle x}$ qui est une entrée de ${\displaystyle s}$ et on construit deux instances plus petites ${\displaystyle s_{0}}$ et ${\displaystyle s_{1}}$ où ${\displaystyle s_{i}}$ correspond à la formule obtenue en remplaçant ${\displaystyle x}$ par la constante ${\displaystyle 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 ${\displaystyle s}$ de SAT pour laquelle ${\displaystyle c(s)}$ est vrai, la procédure d’auto-réduction décrite ci-dessus trouve une solution valide à ${\displaystyle s}$.

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

AM = MA[modifier | modifier le code]

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Références[modifier | modifier le code]

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Karp–Lipton theorem » (voir la liste des auteurs).

• Portail de l'informatique théorique