Les problèmes complets

À l' heure actuelle, la résolution soit une problème -complete ou un P S P A C E problème -complete est impossible dans le cas général pour les grandes entrées. Cependant, les deux peuvent être résolus en temps exponentiel et en espace polynomial.$NP$$PSPACE$

Puisque nous ne pouvons pas construire des ordinateurs non déterministes ou «chanceux», cela nous change-t-il si un problème est complet ou P S P A C E- complet?$NP$$PSPACE$

C’est une très bonne question à laquelle j’ai beaucoup réfléchi: le fait qu’un problème soit complet ou P S P A C E- complet affecte-t-il réellement la complexité du problème dans le pire des cas? $NP$$PSPACE$Plus concrètement, une telle distinction affecte-t-elle réellement la complexité du "cas typique" du problème dans la pratique?

Intuition dit que le problème -complete est plus dur que le N P COMPLETES un, peu importe quelle mesure de la complexité que vous utilisez. Mais la situation est subtile. Il se pourrait, par exemple, que Q B F (formules booléennes quantifiées, le problème complet canonique P S P A C E ) soit en temps subexponentiel si et seulement si S A T (Satisfaisabilité, le N P canonique)$PSPACE$$NP$$QBF$$PSPACE$$SAT$$NP$- problème complet) est en temps subexponentiel. (Une direction est évidente; l'autre direction serait un résultat majeur!) Si cela est vrai, alors peut-être que du point de vue "je veux juste résoudre ce problème", peu importe si le problème est complet ou N P- complet: dans les deux cas, un algorithme sous-exponentiel pour l'un implique un algorithme sous-exponentiel pour l'autre.$PSPACE$$NP$

Laissez-moi être l’avocat du diable et vous donner un exemple dans lequel un problème est "plus dur" que l’autre, mais s’avère néanmoins être "plus facile à traiter" que l’autre.

Soit une formule booléenne sur n variables, où n est pair. Supposons que vous ayez le choix entre deux formules à décider:$F(x_1,\ldots,x_{n})$$n$$n$

.$\Phi_1 = (\exists x_1)(\exists x_2)\cdots (\exists x_{n-1})(\exists x_{n})F(x_1,\ldots,x_{n})$

$\Phi_2 = (\exists x_1)(\forall x_2)\cdots (\exists x_{n-1}(\forall x_{n})F(x_1,\ldots,x_{n})$

(C'est, dans , le suppléant de quantificateurs.)$\Phi_2$

Selon vous, lequel est le plus facile à résoudre? Formules de type ou formules de type Φ 2 ?$\Phi_1$$\Phi_2$

On pourrait penser que le choix évident est , car ce n'est que N P- complet pour le décider, alors que Φ 2 est un problème P S P A C E- complet. Mais en fait, selon nos algorithmes les plus connus, Φ 2 est un problème plus facile. Nous n'avons aucune idée de la façon de résoudre Φ 1 pour le général F en moins de 2 n étapes. (Si nous pouvions le faire, nous aurions nouvelles minorations de taille de la formule!) Mais Φ 2 peut être facilement résolu pour tout F en aléatoire O $\Phi_1$$NP$$\Phi_2$$PSPACE$$\Phi_2$$\Phi_1$$F$$2^n$$\Phi_2$$F$ fois, en utilisant la recherche aléatoire dans l’arbre de jeu! Pour une référence, voir le chapitre 2, section 2.1, dans Motwani et Raghavan.$O(2^{.793 n})$

L'intuition est que l' ajout de quantificateurs universels limite réellement le problème , le rendant plus facile à résoudre que plus difficile. L'algorithme de recherche dans l'arborescence du jeu repose fortement sur l'utilisation de quantificateurs alternatifs et ne peut gérer des quantifications arbitraires. Reste toutefois que les problèmes peuvent parfois devenir "plus simples" avec une mesure de complexité, même s'ils peuvent paraître "plus difficiles" avec une autre mesure.

Cela a de l'importance, car l'enjeu est plus important que de savoir si nous pouvons ou non trouver des solutions. Il est également intéressant de savoir si nous pouvons vérifier les solutions. D'autres distinctions qualitatives peuvent être faites entre la difficulté des problèmes, mais ce serait celle que j'identifierais comme étant la plus importante pour les classes NP plus grandes.

Pour les problèmes de décision - problèmes pour lesquels chaque instance a une réponse « OUI » ou « NON » - NP est précisément la classe de problèmes pour lesquels nous pouvons vérifier efficacement la prétendue preuve qu'une instance donnée est une instance de « OUI », de manière déterministe, si on nous en présente un. Par exemple, si vous avez une affectation satisfaisante de variables pour une instance de 3-SAT, cette affectation vous permet de prouver efficacement que l'instance est satisfiable. Il peut être difficile de trouver une tâche aussi satisfaisante, mais une fois que vous en avez une, vous pouvez facilement prouver aux autres que l’instance est satisfaisante, simplement en leur demandant de vérifier la solution que vous avez trouvée.

De même, pour coNP , il existe des preuves vérifiables de manière efficace pour les instances « NO »; et pour les problèmes dans NP  ∩  coNP , vous pouvez faire les deux. Mais pour PSPACE , des problèmes complets n'existent pas, à moins que vous ne puissiez prouver des égalités assez spectaculaires de classes de complexité.

Nous ne savons pas comment construire des problèmes difficiles de cas moyen à partir de problèmes NP-complets (dans le cas le plus défavorable), mais nous pouvons le faire pour PSPACE (voir Köbler & Schuler (1998) ) afin de créer des problèmes même avec la distribution uniforme impossible à obtenir. résolu sur la plupart des entrées, à moins que tout PSPACE soit facile à calculer.

D'un point de vue pratique, il est important de rappeler que la NP-Completeness n'est pas un obstacle pour de nombreux problèmes dans la pratique. Les outils jumeaux des solveurs SAT et de CPLEX (pour la programmation linéaire entière) sont suffisamment puissants et bien conçus pour qu'il soit souvent possible de résoudre des problèmes volumineux de NP-complets en définissant le problème comme un ILP approprié ou par réduction à la SAT.

Je ne suis pas au courant de solutions aussi bien conçues pour résoudre les problèmes rencontrés dans PSPACE.

Vous pourriez penser de cette façon: un problème mathématique a-t-il une preuve lisible par l'homme, ou nécessite-t-il intrinsèquement une "preuve d'ordinateur". Exemples: la position de départ des contrôleurs est-elle un match nul? (Réponse: oui.) La position de départ des échecs est-elle une victoire pour les blancs? (Réponse: inconnu, mais la plupart des diplômés pensent que c'est un match nul.)

Pour prouver que la position de départ des contrôleurs est un tirage au sort, il faut en fin de compte accepter que l'ordinateur a réellement vérifié avec précision un grand nombre de cas particuliers. Si une preuve concernant les échecs existe, il faudra probablement que les lecteurs humains acceptent qu'un ordinateur vérifie correctement, même dans des cas plus spéciaux. Et il se peut fort bien qu’il n’existe pas de méthode plus courte pour vérifier ces déclarations. Ce sont des problèmes dans PSPACE. Si un problème est "juste" en NP, alors (intuitivement) un être humain pourrait garder toute la preuve dans sa tête. Cet humain pourrait bien être un mathématicien très spécialisé.

$n^{1000000}$

Suite au commentaire de Suresh, il semble y avoir une grande différence dans la pratique. Il existe des heuristiques qui parviennent à exploiter la structure d'instances SAT pratiques et à obtenir d'excellentes performances (je fais référence ici aux résolveurs d'apprentissage de clause basés sur des conflits). La même heuristique ne produit pas d’améliorations similaires des performances dans les solveurs QBF.

La différence entre preuve et vérification apparaît également. Certains solveurs SAT (tels que MiniSAT 1.14 et une foule d'autres) produisent des preuves. Produire des preuves dans les solveurs QBF actuels n'est pas trivial. (La déclaration suivante vient du ouï-dire.) Il existe de nombreux cas dans la compétition QBF sur lesquels les solveurs produisent apparemment des résultats différents. En l'absence de solveurs générateurs de preuves, nous ne savons pas quel résultat est correct.

Si vous examinez les performances pratiques à la SAT et aux échecs, vous constaterez une différence: les problèmes NP-complete sont plus faciles à gérer que les problèmes PSPACE complets. Les solveurs SAT peuvent aujourd'hui gérer plus de mille variables, mais le meilleur moteur d'échecs, dans le même temps, ne peut calculer que moins de 20 coups.

Je suppose que cela est dû à la structure des problèmes. Oui, si vous ne faites qu'énumérer les solutions, la résolution SAT est extrêmement lente. Mais comme il n’a pas l’alternance du quantificateur, les gens découvrent des structures dans la formule et évitent ainsi beaucoup d’énumération. Je pense que Ryan Williams a négligé ce point.

Avec l’alternance des quantificateurs, oui, il existe des méthodes intelligentes d’élagage, mais la structure n’est pas aussi riche que celle d’une formule CNF.

Laisse-moi prédire l'avenir. La résolution SAT le fera en examinant la formule et en évitant essentiellement les recherches, tandis que les échecs le feront en capitalisant les recherches dans l’arbre de jeu.