Montrer qu'un problème dans X n'est pas X-Complete

18

La théorie existentielle des réels est dans PSPACE , mais je ne sais pas si elle est PSPACE-Complete . Si je crois que ce n'est pas le cas, comment pourrais-je le prouver?

Plus généralement, étant donné un problème dans une classe de complexité X , comment puis-je montrer qu'il n'est pas X-Complete ? Par exemple, X pourrait être NP , PSPACE , EXPTIME .

Dave Clarke
la source
Bien sûr, ce n'est pas facile et personne ne peut fournir de réponse pour votre partie générale :-) J'ai trop de problèmes, je sais qu'ils sont NP, mais je ne sais pas qu'ils sont NP-Complete ou pas (ni trop d'autres personnes).

Réponses:

16

En fait, prouver que X n'est pas PSPACE -complet (sous, disons, les réductions du temps polynomial) serait extrêmement difficile à faire.

Si P=PSPACE , alors tous les problèmes non triviaux (c'est-à-dire non et non Σ ) et infinis dans PSPACE sont PSPACE -complets sous des réductions de temps polynomiales. Puisque la théorie existentielle des réels a cette propriété non triviale et infinie, prouver qu'elle n'est pas PSPACE -complète impliquerait PPSPACE. (Voir la réponse à cette question sur CSTheory.SE pour un croquis de la preuve.)

Ryan Williams
la source
1
On dirait certainement que j'ai mordu plus que je ne peux mâcher, pour ainsi dire.
Dave Clarke
11

Un problème dans n'est pas X- complet s'il y a d'autres problèmes dans X qui ne peuvent pas être réduits à cela. Une méthode simple (mais peut-être efficace uniquement sur des exemples triviaux) serait de prouver que votre problème se trouve également dans une autre classe de complexité Y telle que Y XXXXYYX .

Par exemple, si vous voulez montrer que votre problème n'est pas complet, il suffit de montrer qu'il est dans P , puisque P E X P T I M E . Cependant, si l' on voulait montrer qu'un problème n'est pas N P -complete, alors il est pas nécessairement suffisante pour montrer qu'il est en P , car on ne sait pas si oui ou non P = N P .EXPTIMEPPEXPTIMENPPP=NP

Joe
la source
3

Comme l'a écrit Ryan, il n'est pas facile de prouver qu'un problème n'est pas difficile.

Que un problème dans une classe de complexité X et S est fermé wrt réductions. Prouver que Q n'est pas X- dur wrt équivaut à séparer la classe de complexité obtenue en prenant la fermeture de Q wrt . Maintenant, si Q est difficile pour une autre classe Y wrt , alors cela signifie que la séparation Y de X . Comme vous le savez, il n'y a pas beaucoup de résultats de séparation.QXSQXQQYYX

Dans votre cas, , = P m et Y = PX=PSpace≤=mPY=P .

Parce que nous ne pouvons pas prouver de tels résultats pour le moment (à l'exception possible de Ryan :), au lieu de prouver que n'est pas X- dur, nous montrons qu'il est dans une classe de complexité qui est censée être plus petite que X . Par exemple, si vous montrez que T h ( R , + , × , 0 , 1 ) est dans P H , alors cela sera considéré comme une preuve solide que Q n'est pas XQXXTh(R,+,×,0,1)PHQX-difficile. (Dans le langage des logiciens, si vous ne pouvez pas prouver un résultat inconditionnel, essayez de prouver un résultat conditionnel en supposant un énoncé difficile à prouver mais largement admis comme ).PPSpace

Kaveh
la source