Consecuencias de un algoritmo de destilación para PSPACE

9

La siguiente noción de un algoritmo de destilación proviene de "En problemas sin núcleos polinomiales".

Deje que se le dé una lenguaUn algoritmo de destilación para toma una lista dada de cadenas de entrada y calcula una cadena de salida tal que:L { x i } i [ t ] yLL{xi}i[t]y

(1) si y solo si existe tal quei [ t ] x iLyLi[t]xiL

(2) para algunos polinomiosp|y|p(Maxi[t]|xi|)p

(3) El algoritmo calcula en la mayoría de las veces para algún polinomioq ( i [ t ] | x i | ) qyq(i[t]|xi|)q

Se ha demostrado que si existe un algoritmo de destilación para un completo de , entonces . Por otra parte, .c o N P N P / p o l y P H = Σ 3NPcoNPNP/polyPH=Σ3

Ver detalles y discusión en:

  • "Inviabilidad de compresión de instancias y PCP sucintas para NP"
  • "Sobre problemas sin núcleos polinomiales"
  • "Límites inferiores en la kernelización"

Preguntas:

  • ¿Podría existir un algoritmo de destilación para un problema completo de ?PSPACE
  • Si existiera tal algoritmo, ¿qué consecuencias de complejidad obtendríamos?
Michael Wehar
fuente
Cualquier otra referencia es bienvenida. ¡Gracias! :)
Michael Wehar
1
En este artículo y en las reducciones de tiempo polinomial muchos, "si existe un algoritmo de destilación para un completo, entonces" NP coAM y "hay pruebas estadísticas no uniformes de conocimiento cero para todos los idiomas en NP ". NP
@RickyDemer ¡Esto es genial! Gracias por compartir. :)
Michael Wehar
1
Ahora me doy cuenta de que el documento al que me vinculé solo necesita compresión , lo que hace que sus resultados sean más generales. En particular, según los Teoremas 7.1 y 7.3, si existe incluso un "algoritmo de compresión para un problema completo de ", entonces PSPACE tiene pruebas estadísticas no uniformes de conocimiento cero. PSPACE
3
No entiendo la última parte de la pregunta. AFAICS la existencia de un algoritmo de destilación para un problema completo de PSPACE no implica la existencia de un algoritmo de destilación para un problema completo de NP, ¿o me estoy perdiendo algo?
Emil Jeřábek

Respuestas:

3

El teorema 15.3 del reciente libro de texto "Algoritmos parametrizados" de Cygan et al. establece lo siguiente:

"Sea dos idiomas. Si existe una destilación OR de L en R, entonces " L c o N P / p o l yL,RΣLcoNP/poly

Entonces, creo que si existe una destilación OR de un lenguaje completo de PSPACE para sí mismo, entonces , es decir, no solo el colapso de la jerarquía polinómica, sino que también PSPACE colapsa con él.P S P A C E c o N P / p o l yLPSPACEcoNP/poly

Michael Lampis
fuente
2
El teorema 7.1 del artículo al que me vinculé en los comentarios es estrictamente cualitativamente mejor. ¿El Teorema 15.3 de ese libro maneja límites de error mayores para algunos parámetros que el ítem 2 de 7.1?
Decías "también PSPACE se derrumba con él". En particular, creo que obtenemos . No veo una manera de mejorar esto, pero pensé en preguntar de todos modos. ¿Podemos obtener un colapso mejor que este? Diga ? Σ 2 = P S P A C EΣ3=PSPACEΣ2=PSPACE
Michael Wehar