Mostrando che un problema in X non è X-Complete

Question

Il esistenziale Teoria dei reali è in PSPACE , ma non so se sia PSPACE-completa . Se credo che non sia il caso, come potrei dimostrarlo?

Più in generale, dato un problema in qualche classe di complessità X , come posso dimostrare che è non X-Completa ? Ad esempio, X potrebbe essere NP , PSPACE , EXPTIME .

Answer 1

In realtà dimostrando $ X $ non è $ PSPACE $ Completa (sotto, per esempio, la riduzione in tempo polinomiale) sarebbe estremamente difficile da fare.

Se $ P = PSPACE $, allora tutto non banale (cioè, non $ \ varnothing $ e non $ \ Sigma ^ {\ stella} $) e problemi infiniti a $ PSPACE $ sono $ PSPACE $ -Complete sotto polinomiale riduzioni -time. Dal momento che la teoria esistenziale dei reali ha questa proprietà non banale e infinito, dimostrando che non è $ PSPACE $ -Complete implicherebbe $ P \ neq PSPACE $. (Vedere la risposta a questa domanda su CSTheory.SE per uno schizzo della prova.)

Answer 2

Un problema in $ X $ non è $ X $ -Complete se ci sono altri problemi in $ X $, che non possono essere ridotte ad esso. Un semplice (ma forse efficace solo su esempi banali) metodo sarebbe dimostrando il vostro problema è anche in qualche altra classe di complessità $ y $ tale che $ y \ sottoinsieme X $.

Per esempio, se si desidera mostrare che il problema non $ EXPTIME $ è completa, allora è sufficiente a dimostrare che è in $ P $, dal momento che $ P \ subsetneq EXPTIME $. Tuttavia, se si voleva dimostrare che un problema non è di $ NP $ -Complete, allora non è necessariamente sufficiente a dimostrare che è in $ P $, dal momento che non si sa se o meno $ P = NP $.

Answer 3

Guardate la risposta accettata per questa domanda su MathOverflow, Quali tecniche esistono per dimostrare che un problema non è NP-completo? . Risponde il caso in cui X = NP.

Answer 4

Come Ryan ha scritto, dimostrando che un problema non è difficile, non è facile.

Let $ Q $ essere un problema in una classe di complessità $ X $ e $ S $ è chiuso w.r.t. $ \ leq $ riduzioni. Dimostrando che $ Q $ non è $ X $ -Hard w.r.t. $ \ Leq $ equivale a separare la classe di complessità ottenuto tenendo chiusura di $ Q $ w.r.t. $ \ Leq $. Ora, se $ Q $ è difficile per un'altra classe $ Y $ w.r.t. $ \ Leq $, allora significa separazione $ Y $ da $ X $. Come sapete, non ci sono molti risultati di separazione.

Nel tuo caso, $ X = \ {mathsf PSpace} $, $ \ leq = \ leq ^ \ mathsf {P} _m $ e $ Y = \ mathsf {P} $.

Perché non possiamo dimostrare tali risultati al momento (con la possibile eccezione di Ryan :), in luogo di dimostrare che $ Q $ non è $ X $ -Hard, dimostriamo che è in una classe di complessità che credevano per essere più piccolo di $ X $. Ad esempio, se si mostra che $ \ mathrm {Th} _ \ esiste (\ mathbb {R, +, \ volte, 0,1}) $ è in $ \ {mathsf PH} $, allora sarà preso come un forte evidenza per $ Q non essendo $ $ X $ -Hard. (Nel linguaggio logici, se non si può dimostrare un risultato senza condizioni, provare dimostrando uno condizionale assumendo un difficile da dimostrare, ma dichiarazione ampiamente creduto come $ \ mathsf {P} \ neq \ mathsf {PSpace} $).