Mostrando que um problema no X não é X-Complete

A teoria existencial dos reais está no PSPACE , mas não sei se é completo no PSPACE . Se eu acredito que não é o caso, como eu poderia provar isso?

De modo mais geral, dado um problema de alguma complexidade classe X , como posso mostrar que é não -X completo ? Por exemplo, X pode ser NP , PSPACE , EXPTIME .

Realmente provar que não é P S P A C E (completo, digamos, reduções no tempo polinomial) seria extremamente difícil de fazer.$X$$PSPACE$

Se , todos os problemas não triviais (isto é, não ∅ e não Σ ⋆ ) e infinitos em P S P A C E são P S P A C E completos em reduções de tempo polinomiais. Como a teoria existencial dos reais possui essa propriedade não trivial e infinita, provar que não é P S P A C E - completo implicaria P ≠ P S P A $P=PSPACE$$\varnothing$$\Sigma^{\star}$$PSPACE$$PSPACE$ $PSPACE$ . (Vejaa resposta a esta pergunta no CSTheory.SEpara um esboço da prova.)$P \neq PSPACE$

Um problema no não é X completo se houver outros problemas no X que não possam ser reduzidos a ele. Um método simples (mas possivelmente apenas eficaz em exemplos triviais) seria provando o seu problema é também de alguma outra classe de complexidade Y tal que Y ⊂ X .$X$$X$$X$$Y$$Y \subset X$

Por exemplo, se você quer mostrar que o seu problema não é completa, então é suficiente para mostrar que ele está em P , desde P ⊊ E X P T I M E . No entanto, se você queria mostrar que um problema não é N P -completo, então não é necessariamente suficiente para mostrar que ele está em P , uma vez que não se sabe se ou não P = N P .$EXPTIME$$P$$P \subsetneq EXPTIME$$NP$$P$$P = NP$

Veja a resposta aceita para esta pergunta no MathOverflow: Quais técnicas existem para mostrar que um problema não está completo no NP? . Responde ao caso quando X = NP.

Como Ryan escreveu, provar que um problema não é difícil não é fácil.

Seja um problema em uma classe de complexidade X e S é fechado com reduções ≤ . Provar que Q não é X -hard wrt ≤ é equivalente a separar a classe de complexidade obtida ao encerrar Q wrt ≤ . Agora, se Q é difícil para uma outra classe Y wrt ≤ , então isso significa que separa Y de X . Como você sabe, não há muitos resultados de separação.$Q$$X$$S$$\leq$$Q$$X$$\leq$$Q$$\leq$$Q$$Y$$\leq$$Y$$X$

No seu caso, , ≤ = ≤ P m , e Y = P .$X = \mathsf{PSpace}$$\leq = \leq^\mathsf{P}_m$$Y=\mathsf{P}$

Como não podemos provar esses resultados no momento (com a possível exceção de Ryan :), em vez de provar que não é X -hard, mostramos que ele está em uma classe de complexidade que se acredita ser menor que X . Por exemplo, se você mostrar que T h ∃ ( R , + , × , 0 , 1 ) está em P H , será considerado uma forte evidência de Q não ser $Q$$X$$X$$\mathrm{Th}_\exists(\mathbb{R,+,\times,0,1})$$\mathsf{PH}$$Q$$X$-Difícil. (Na linguagem dos lógicos, se você não puder provar um resultado incondicional, tente provar um condicional assumindo uma afirmação difícil de provar, mas amplamente aceita como ).$\mathsf{P}\neq\mathsf{PSpace}$