Mostrar que un problema en X no es X-Complete

La teoría existencial de los Reales está en PSPACE , pero no sé si es PSPACE-Complete . Si creo que no es así, ¿cómo podría probarlo?

De manera más general, dado un problema en cierta complejidad clase X , ¿cómo puedo demostrar que es no X-Completa ? Por ejemplo, X podría ser NP , PSPACE , EXPTIME .

En realidad, probar que no es P S P A C E -completo (bajo, digamos, reducciones de tiempo polinomial) sería extremadamente difícil de hacer.$X$$PSPACE$

Si , entonces todos los problemas no triviales (es decir, no ∅ y no Σ ⋆ ) e infinitos en P S P A C E son P S P A C E -completo bajo reducciones de tiempo polinomial. Dado que la teoría existencial de los reales tiene esta propiedad no trivial e infinita, probar que no es P S P A C E -completo implicaría P ≠ P S P A $P=PSPACE$$\varnothing$$\Sigma^{\star}$$PSPACE$$PSPACE$ $PSPACE$ . (Consultela respuesta a esta pregunta en CSTheory.SEpara ver un boceto de la prueba).$P \neq PSPACE$

Un problema en no es X- completo si hay otros problemas en X que no se pueden reducir a él. Un método sencillo (pero posiblemente sólo es eficaz en ejemplos triviales) estaría demostrando su problema es también de alguna otra clase de complejidad Y tal que Y ⊂ X .$X$$X$$X$$Y$$Y \subset X$

Por ejemplo, si desea mostrar que su problema no es completa, entonces es suficiente para mostrar que está en P , ya que P ⊊ E X P T I M E . Sin embargo, si se quería demostrar que no es un problema N P -Complete, entonces no es necesariamente suficiente para mostrar que está en P , ya que no se sabe si o no P = N P .$EXPTIME$$P$$P \subsetneq EXPTIME$$NP$$P$$P = NP$

Mire la respuesta aceptada para esta pregunta en MathOverflow, ¿Qué técnicas existen para mostrar que un problema no es NP completo? . Responde el caso cuando X = NP.

Como escribió Ryan, probar que un problema no es difícil no es fácil.

Sea un problema en una clase de complejidad X y S está cerrado wrt ≤ reducciones. Probar que Q no es X -duro wrt ≤ es equivalente a separar la clase de complejidad obtenida al cerrar Q wrt ≤ . Ahora, si Q es difícil para otra clase Y wrt ≤ , entonces significa separar $Q$$X$$S$$\leq$$Q$$X$$\leq$$Q$$\leq$$Q$$Y$$\leq$$Y$ de . Como sabes, no hay muchos resultados de separación.$X$

En su caso, , ≤ = ≤ P m , y$X = \mathsf{PSpace}$$\leq = \leq^\mathsf{P}_m$ .$Y=\mathsf{P}$

Debido a que no podemos probar tales resultados en este momento (con la posible excepción de Ryan :), en lugar de probar que no es X- duro, mostramos que está en una clase de complejidad que se cree que es menor que X . Por ejemplo, si muestra que T h ∃ ( R , + , × , 0 , 1 ) está en P H , entonces se tomará como una fuerte evidencia de que Q no es $Q$$X$$X$$\mathrm{Th}_\exists(\mathbb{R,+,\times,0,1})$$\mathsf{PH}$$Q$$X$-difícil. (En el lenguaje de los lógicos, si no puede probar un resultado incondicional, intente probar uno condicional suponiendo una declaración difícil de probar pero ampliamente creída como ).$\mathsf{P}\neq\mathsf{PSpace}$