Montre qu'il ya un problème dans X n'est pas X-Complete

Question

Le Existentielle Théorie des Reals est PSPACE , mais Je ne sais pas si elle est PSPACE- complet . Si je crois que ce n'est pas le cas, comment pourrais-je le prouver?

De manière plus générale, étant donné un problème dans une certaine classe de complexité X , comment puis-je montrer qu'il est pas X-complet ? Par exemple, X pourrait être NP , PSPACE , EXPTIME .

Answer 1

En fait, prouver $ X $ est pas $ PSPACE $ -complete (en, disons, la réduction du temps polynomiale) serait extrêmement difficile à faire.

Si $ P = PSPACE $, alors non-trivial (ie, pas $ \ varnothing $ et $ \ Sigma ^ {\ star} $) et des problèmes infinis en $ PSPACE $ sont $ PSPACE $ -complete sous polynomiale réductions -time. Depuis la théorie existentielle des nombres réels a cette propriété non trivial et infini, ce qui prouve que est pas $ PSPACE $ -complete impliquerait $ P \ NEQ PSPACE $. (Voir la réponse à cette question sur CSTheory.SE pour un croquis de la preuve.)

Answer 2

Un problème de $ X $ est pas $ X $ -complete s'il y a d'autres problèmes de $ X $ qui ne peut être réduit à elle. Un simple (mais peut-être efficace que sur des exemples triviaux) méthode serait prouver votre problème est aussi dans une autre classe de complexité $ Y $ tel que $ Y \ subset X $.

Par exemple, si vous voulez montrer que votre problème n'est pas $ EXPTIME $ complète, il suffit de montrer qu'il est en $ P $, puisque $ P \ subsetneq EXPTIME $. Cependant, si l'on voulait montrer qu'un problème n'est pas $ NP -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 = NP $.

Answer 3

Regardez la réponse acceptée pour cette question sur mathoverflow,

Ryan a écrit, prouvant qu'un problème n'est pas est difficile pas facile.

Soit $ Q $ un problème dans une classe de complexité $ X $ et $ S $ est w.r.t. fermée $ \ leq réductions de $. Prouver que $ Q $ est pas $ X $ -hard w.r.t. $ \ Leq $ est équivalente à la séparation de la classe de complexité obtenue en prenant la fermeture de $ Q $ w.r.t. $ \ Leq $. Maintenant, si $ Q $ est difficile pour une autre classe $ Y w.r.t. de $ $ \ Leq $, alors cela signifie que la séparation Y $ $ de $ X $. Comme vous le savez, il n'y a pas de résultats de séparation.

Dans votre cas, $ X = \ mathsf {PSpace} $, $ \ leq = \ leq ^ \ mathsf {P} _m $, et $ Y = \ mathsf {P} $.

Parce que nous ne pouvons pas prouver de tels résultats au moment (à l'exception possible de Ryan :), en place de prouver que $ Q $ est pas $ X $ -hard, nous montrons qu'il est dans une classe de complexité est cru pour être plus petite que $ X $. Par exemple, si vous montrez que $ \ mathrm {Th} _ \ existe (\ mathbb {R, +, \ fois, 0,1}) $ est en $ \ mathsf {PH} $, alors il sera considéré comme un des preuves solides pour $ Q $ ne pas être $ X $ -hard. (Dans la langue de logiciens, si vous ne pouvez pas prouver un résultat inconditionnel, essayez de prouver une condition supposant un difficile à prouver, mais la déclaration largement cru comme $ \ mathsf {P} \ neq \ mathsf {PSpace} $).

Answer 4

Answer 5

Answer 6

Ryan a écrit, prouvant qu'un problème n'est pas est difficile pas facile.

Soit $ Q $ un problème dans une classe de complexité $ X $ et $ S $ est w.r.t. fermée $ \ leq réductions de $. Prouver que $ Q $ est pas $ X $ -hard w.r.t. $ \ Leq $ est équivalente à la séparation de la classe de complexité obtenue en prenant la fermeture de $ Q $ w.r.t. $ \ Leq $. Maintenant, si $ Q $ est difficile pour une autre classe $ Y w.r.t. de $ $ \ Leq $, alors cela signifie que la séparation Y $ $ de $ X $. Comme vous le savez, il n'y a pas de résultats de séparation.

Dans votre cas, $ X = \ mathsf {PSpace} $, $ \ leq = \ leq ^ \ mathsf {P} _m $, et $ Y = \ mathsf {P} $.

Parce que nous ne pouvons pas prouver de tels résultats au moment (à l'exception possible de Ryan :), en place de prouver que $ Q $ est pas $ X $ -hard, nous montrons qu'il est dans une classe de complexité est cru pour être plus petite que $ X $. Par exemple, si vous montrez que $ \ mathrm {Th} _ \ existe (\ mathbb {R, +, \ fois, 0,1}) $ est en $ \ mathsf {PH} $, alors il sera considéré comme un des preuves solides pour $ Q $ ne pas être $ X $ -hard. (Dans la langue de logiciens, si vous ne pouvez pas prouver un résultat inconditionnel, essayez de prouver une condition supposant un difficile à prouver, mais la déclaration largement cru comme $ \ mathsf {P} \ neq \ mathsf {PSpace} $).

Answer 7

Answer 8

Answer 9