Les problèmes complets

66

À 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.NPPSPACE

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?NPPSPACE

Alex ten Brink
la source

Réponses:

82

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? NPPSPACEPlus 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)PSPACENPQBFPSPACESATNP- 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.PSPACENP

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(x1,,xn)nn

.Φ1=(x1)(x2)(xn1)(xn)F(x1,,xn)

Φ2=(X1)(X2)(Xn-1(Xn)F(X1,,Xn)

(C'est, dans , le suppléant de quantificateurs.)Φ2

Selon vous, lequel est le plus facile à résoudre? Formules de type ou formules de type Φ 2 ?Φ1Φ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 (Φ1NPΦ2PSPUNECEΦ2Φ1F2nΦ2F 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.793n)

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.

Ryan Williams
la source
16
Bonne réponse et prise intéressante.
Suresh Venkat
Il me semble que ce qui précède est un assez bon exemple de ce que nous entendons par "complexité fine" (programme de l'automne 2015 à l'Institut Simons). Une des idées clés est que la théorie de la complexité peut sembler très différente lorsque, au lieu d'essayer de trouver pour chaque problème un modèle de calcul (potentiellement bizarre) pour lequel ce problème est "complet", on se concentre simplement sur la compréhension du meilleur temps d'exécution possible. exposant pour le problème.
Ryan Williams le
37

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

Niel de Beaudrap
la source
Je pense que la question concerne "l'optimisation" de la version de NP-complete et de PSPACE-complete. Par exemple, y a-t-il une différence (en termes de complexité) entre trouver une solution pour SAT et pour QBF? Et plus généralement, existe-t-il une caractérisation des problèmes d'optimisation dont la version de décision est NP-complete ou PSPACE-complete?
Lamine
@Lamine: Je ne détecte pas la distinction que vous faites dans la question (au moins, entre une simple décision et une optimisation complète). Vous voulez peut-être dire que le demandeur ne s'intéresse qu'à la question des ressources nécessaires pour trouver la réponse et ne s'intéresse pas aux autres mesures de difficulté du problème, auquel cas je conviens que ma réponse ne répond pas à cela. Dans tous les cas, voici ma réponse à la question telle qu'elle est.
Niel de Beaudrap
5
Très belle réponse.
Dave Clarke
La capacité de vérifier efficacement n’aide pas à calculer une solution (sauf si P = NP). NP et co-NP permettent d’attaquer le problème en utilisant la méthode de recherche et vérification. Cette approche est facile à mettre en œuvre et peut même être plus efficace, mais elle n’aide en rien.
András Salamon
@ András: c'est vrai - c'est pourquoi je souligne que la recherche de solutions n'est pas la seule chose importante dans la préface de ma réponse.
Niel de Beaudrap
36

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.

Lance Fortnow
la source
20

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.

Suresh Venkat
la source
11
Il y a un concours annuel conçu pour améliorer les solveurs QBF . Je ne les ai pas beaucoup utilisés.
Radu GRIGore
7

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

n1000000

Aaron Sterling
la source
Peut-on également soutenir que les problèmes complets du coNP ont ce problème de nécessiter (parfois) une "preuve informatique"?
Philip White
@Philip White: Je ne pense pas que ce soit la même chose. Dites "un match nul aux échecs" est en coNP. Pour dire non, tout ce que je dois faire, c'est démontrer une seule ligne de forçage facilement vérifiable. Cependant, nous nous attendons à ce que, même si une telle ligne existe, il sera probablement très difficile de prouver qu’il s’agit bien de "forcer". Le problème ne donne donc aucune garantie de simplicité s'il peut être résolu dans une direction donnée. "Les échecs sont un tirage au sort" nécessite probablement de manière inhérente un ordinateur pour prouver, que ce soit vrai ou faux.
Aaron Sterling
5

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.

Vijay D
la source
0

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.

Zirui Wang
la source