Demostrando que un problema en X no es X-Completa

Question

El existencial Teoría de los reales está en PSPACE , pero no sé si se trata de PSPACE-completa . Si yo creo que no es el caso, ¿cómo podría demostrarlo?

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

Answer 1

En realidad probando $ X $ $ no es PSPACE $ -Complete (bajo, por ejemplo, reducciones de tiempo polinómico) sería extremadamente difícil de hacer.

Si $ P = $ PSPACE, entonces todo no trivial (es decir, no $ \ $ varnothing y no $ \ sigma ^ {\ estrella} $) y los problemas infinitos en PSPACE $ $ $ son PSPACE $ -Complete bajo polinomio reducciones -time. Desde la teoría existencial de los reales tiene esta propiedad no trivial e infinito, demostrando que no es $ PSPACE $ -Complete implicaría $ P \ neq PSPACE $. (Véase la respuesta a esta pregunta en CSTheory.SE para un boceto de la prueba.)

Answer 2

Un problema en $ X $ no es $ X $ -Complete si hay algún otro problema en $ X $, que no pueden ser reducidos a la misma. Una sencilla (pero posiblemente sólo es eficaz en ejemplos triviales) Método estaría demostrando su problema es también de alguna otra clase de complejidad $ Y $ tal que $ S \ subset X $.

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

Answer 3

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

Answer 4

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

Vamos a $ Q $ es un problema en una clase de la complejidad $ X $ y $ S $ es w.r.t. cerrada $ \ leq $ reducciones. Demostrando que $ Q $ no es $ X $ -Hard w.r.t. $ \ Leq $ es equivalente a la separación de la clase de la complejidad obtenida mediante la adopción de cierre de $ Q $ w.r.t. $ \ Leq $. Ahora bien, si $ Q $ es difícil para otra clase $ Y $ w.r.t. $ \ Leq $, entonces significa que la separación de $ Y $ de $ X $. Como ya saben, no hay muchos resultados de separación.

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

Debido a que no podemos probar estos resultados en el momento (con la posible excepción de Ryan :), en lugar de probar que $ Q $ no es $ X $ -Hard, se muestra que se encuentra en una clase de complejidad que es creyeron a ser menor que $ X $. Por ejemplo, si usted demuestra que $ \ mathrm {Th} _ \ existe (\ mathbb {R, +, \ veces, 0,1}) $ está en $ \ mathsf {PH} $, entonces se toma como una fuerte evidencia de $ Q $, no siendo X $ $ -Hard. (En el lenguaje lógicos, si no se puede demostrar un resultado incondicional, trate de probar un condicional asumiendo una difícil de probar pero la declaración cree ampliamente como $ \ mathsf {P} \ neq \ mathsf {PSPACE} $).