¿Hay alguna consecuencia de la existencia de $ \ mathsf {pspace} $ - lenguaje escaso completo como con el teorema de Mahaney?

Question

El teorema de Mahaney afirma que la existencia de $ \ mathsf {np} $ -completa lenguaje escaso conduciría a $ \mathsf {p= np} $ .¿Hay algún resultado como resultado con respecto a la misma para la clase de complejidad $ \ mathsf {pspace} $ , como "Si hay un $ \ mathsf {pspace} $ -complete language escaso, $ \ mathsf {pp= pspace} $ "o lo mismo para cualquier otra clase de complejidad dentro de $ \ mathsf {pspace} $ ?

Answer 1

Un resultado rápido es que $ PSPACE=SIGMA_2 $ .

Primero Mostrar que $ PSPACE \ Subesteq P / Poly $ , y como resultado $ pspace \ subesteq \ sigma_2 $ (Si encuentra una entrada de una tabla de cómputo está en P / POLY, también está en $ \ sigma_2 $ , ya que podemos adivinar un circuito y Verifique localmente su corrección como se describe aquí ).

Para ver por qué tener un lenguaje escaso completo de PSPAIPE $ s $ pone PSPACE en P / Poly, Dado $ l \ en PSPACE $ , deje que $ f $ sea una reducción de $ l $ a < Span Class="Math-contenedor"> $ s $ . Tenga en cuenta que si $ | f (x) | $ depende solo de $ | x | $ , luego < Span Class="Math-contenedor"> $ l \ en P / POLY $ Dado que podemos concatenar los circuitos para $ f $ y para $ s $ (que está en P / Poly debido a ser escaseado). Para superar el hecho de que $ f $ puede variar en la longitud de la salida para el mismo tamaño de entrada, tenga en cuenta que en la longitud $ n $ entradas $ f $ puede producir una salida de longitud $ \ le n ^ c $ , por lo que Dado $ x $ Podemos tomar como un sugerir todo $ | x | ^ C $ circuitos para $ s $ en tamaños de entrada $ 0,1, ..., | x | ^ C $ . Entre estos circuitos, tenemos el circuito "correcto" que puede determinar la membresía de $ f (x) $ a $ S $ .