He visto que P! = LINSPACE (con lo que me refiero a SPACE (n)), pero que no sabemos si uno es un subconjunto del otro.
Supongo que eso significa que la prueba no debe implicar mostrar un problema que está en una clase pero no en la otra, entonces, ¿de qué otra manera podría probarlo?
¡Gracias!
Suponga por contradicción que P = ESPACIO (n). Esto significa que la reducción del tiempo polinómico es equivalente a la reducción del espacio lineal. Por lo tanto, TQBF es PSPACE completo en términos de ambas reducciones. Dado que TQBF$\in$ SPACE (n), concluimos que PSPACE = SPACE (n) = P, lo que contradice el teorema de la jerarquía espacial.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
