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

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 .

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 $\varnothing$ et non $\Sigma^{\star}$ ) 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 $P \neq PSPACE$. (Voir la réponse à cette question sur CSTheory.SE pour un croquis de la preuve.)

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 ⊂ $X$$X$$X$$Y$$Y \subset X$ .

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 .$EXPTIME$$P$$P \subsetneq EXPTIME$$NP$$P$$P = NP$

Regardez la réponse acceptée pour cette question sur MathOverflow, Quelles techniques existent pour montrer qu'un problème n'est pas complet en NP? . Il répond au cas où X = NP.

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.$Q$$X$$S$$\leq$$Q$$X$$\leq$$Q$$\leq$$Q$$Y$$\leq$$Y$$X$

Dans votre cas, , ≤ = ≤ P m et Y = $X = \mathsf{PSpace}$$\leq = \leq^\mathsf{P}_m$$Y=\mathsf{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 $Q$$X$$X$$\mathrm{Th}_\exists(\mathbb{R,+,\times,0,1})$$\mathsf{PH}$$Q$$X$-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 ).$\mathsf{P}\neq\mathsf{PSpace}$