Teorema de Ladner generalizado

45

El teorema de Ladner establece que si P ≠ NP, entonces hay una jerarquía infinita de clases de complejidad que contienen estrictamente P y estrictamente contenidas en NP. La prueba utiliza la integridad de SAT bajo reducciones de muchos en NP. La jerarquía contiene clases de complejidad construidas por una especie de diagonalización, cada una de las cuales contiene un lenguaje en el que los idiomas de las clases inferiores no son reducibles para muchos.

Esto motiva mi pregunta:

Sea C una clase de complejidad y D sea una clase de complejidad que contenga estrictamente C. Si D contiene lenguajes que están completos para alguna noción de reducción, ¿existe una jerarquía infinita de clases de complejidad entre C y D, con respecto al ¿reducción?

Más específicamente, me gustaría saber si hay resultados conocidos para D = P y C = LOGCFL o C = NC , para una noción apropiada de reducción.


El artículo de Ladner ya incluye el Teorema 7 para las clases delimitadas por el espacio C, como Kaveh señaló en una respuesta. En su forma más fuerte, esto dice: si NL ≠ NP, entonces hay una secuencia infinita de idiomas entre NL y NP, de dureza estrictamente creciente. Esto es un poco más general que la versión habitual (Teorema 1), que está condicionado a P ≠ NP. Sin embargo, el artículo de Ladner solo considera D = NP.

András Salamon
fuente
1
Primero se puede hacer la pregunta enfocándose en clases que ya sabemos difieren. Por ejemplo, ¿existe una jerarquía infinita entre AC 0 y AC 0 [6], con respecto a las proyecciones? ¡Esa parece una pregunta difícil! :-)00
Michaël Cadilhac
Consulte también cstheory.stackexchange.com/questions/52/… para obtener una pregunta sobre el intervalo de P a NP.
András Salamon

Respuestas:

33

La respuesta a su pregunta es "sí" para una amplia variedad de clases y reducciones, incluidas las reducciones de espacio de registro y las clases que mencionó, como se demuestra en estos documentos:

H. Vollmer. La técnica del lenguaje gap revisitada . Computer Science Logic, Lecture Notes in Computer Science vol. 533, páginas 389-399, 1990.

K. Regan y H. Vollmer. Gap-languages ​​y clases de complejidad de tiempo de registro . Informática teórica, 188 (1-2): 101-116, 1997.

(Puede descargar archivos postscript comprimidos de estos documentos aquí ).

Las pruebas siguen el principio básico de la extensión de Uwe Schöning del teorema de Ladner:

Uwe Schöning. Un enfoque uniforme para obtener conjuntos diagonales en clases de complejidad . Informática teórica 18 (1): 95-103, 1982.

La prueba de Schöning siempre ha sido mi prueba favorita del teorema de Ladner: es simple y general.

John Watrous
fuente
¿Y qué hay de las clases de promesa?
Marcos Villagra
12

Es muy probable que pueda lograr esto en una configuración genérica. Es casi seguro que tal resultado ya se ha probado en un entorno genérico, pero las referencias se me escapan en este momento. Así que aquí hay un argumento desde cero.

El informe en http://oldblog.computationalcomplexity.org/media/ladner.pdf tiene dos pruebas del teorema de Ladner. La segunda prueba, por Russell Impagliazzo, produce un lenguaje de la forma { x 01 f ( | x | ) } donde x codifica una fórmula satisfactoria yf es una función computable de tiempo polinomial particular. Es decir, simplemente rellenando SAT con el número apropiado de 1 's, puede obtener conjuntos "NP-intermedios". El relleno se realiza para "diagonalizar" sobre todas las reducciones de tiempo polinomiales posibles, de modo que no se reduzca el tiempo polinomial de SAT a L 1L1x01f(|x|)xf1L1funcionará (suponiendo ). Para demostrar que hay infinitos grados de dureza, uno debería poder sustituir L 1 en lugar de SAT en el argumento anterior, y repetir el argumento para L 2 = { x 0 1 f ( | x | ) | x L 1 }. Repita con L i = { x 0 1 f ( | x | ) | x L i -PNPL1L2=x01f(|x|)|xL1Li= }.x01f(|x|)|xLi1

Parece claro que tal prueba se puede generalizar a las clases y D , donde (1) C está contenido adecuadamente en D , (2) D tiene un lenguaje completo bajo las reducciones de C , (3) la lista de todas las reducciones de C puede ser de forma recursiva enumerado, y (4) la función f es computable en C . Quizás el único requisito preocupante es el último, pero si observa la definición de f en el enlace, parece muy fácil de calcular, para las clases C más razonables que se me ocurren.CDCDDCCfCfC

Ryan Williams
fuente
8

Creo que la respuesta es positiva para y la versión uniforme de N C . La prueba de Ladner no usa mucho más que lo que usted dijo y el hecho de que la clase más pequeña está representada recursivamente y debería funcionar con modificaciones menores, pero no he verificado los detalles, eche un vistazo a la reseña de Lance aquí .C=LnorteC


Actualizar

Consulte el documento de Ladner sobre la estructura de la reducibilidad del tiempo polinomial

Aquí está el resumen: Cook y Karp definieron dos nociones de reducibilidad de tiempo polinomial, denotadas aquí por y P m , respectivamente. Se investiga la propiedad abstracta de estas dos relaciones en el dominio de los conjuntos computables. Ambas relaciones demuestran ser densas y tener pares mínimos. Además, hay una secuencia estrictamente ascendente con un par mínimo de límites superiores a la secuencia. Nuestro método de mostrar la densidad produce el resultado de que si P N P, entonces hay miembros de N P - P que no son polinomios completos.TPAGSmetroPAGSPAGSnortePAGSnortePAGS-PAGS

Teorema 1. Si B es computable y no en entonces existe un computable A tal que A P , A P m B , y B P T A .PAGSUNAUNAPAGSUNAmetroPAGSsisiTPAGSUNA

También vea la sección 6 que discute las generalizaciones:

Teorema 5. Si es una clase de tiempo entonces C m y C T son las relaciones y teoremas reflexivas y transitivos 1-4 asimiento con P reemplazado por C .CmetroCTCPAGSC

Teorema 7. Si es una clase de espacio entonces C m y C T son las relaciones y teoremas reflexivas y transitivos 1-4 asimiento con P reemplazado por C .CmetroCTCPAGSC

Los términos clase de tiempo y clase de espacio se definen en el documento.

Kaveh
fuente
Según entendí las pruebas Ladner e Impagliazzo, parecían usar algunos ingredientes específicos para NP, SAT y muchas reducciones de tiempo polinomial. Mi pregunta es precisamente sobre si esos ingredientes se pueden usar de manera más general.
András Salamon
@ András Salamon: No, en realidad la prueba original de Ladner no utiliza ningún hecho sobre el SAT que sea computable (ver el teorema 1 arriba). En la sección 6, analiza las propiedades requeridas para que una reducción funcione para sus teoremas. Creo que es una clase espacial. L
Kaveh
Creo que el teorema también se puede generalizar a clases de circuito uniformes, por lo que el teorema 1 también funcionaría para (no he verificado los detalles, lo agregaré a la publicación cuando lo haga o encuentre una referencia), pero no No creo que pueda generalizarse a versiones no uniformes, ya que la prueba utiliza el hecho de que la clase de complejidad se representa de forma recursiva. Sería interesante saber si el teorema 1 también se cumple para C = A C 0 (versión uniforme) que respondería al comentario de Michaël Cadilhac debajo de la publicación. C=norteCC=UNAC0 0
Kaveh
5

Hice una pregunta similar a Peter Shor en Mathoverflow aquí . Según él, no tiene conocimiento de tal resultado.

nortePAGSPAGS

UNAyopagssiyo-1pagssi

Otro problema interesante es considerar una generalización de Ladner a las versiones prometedoras de clases semánticas, como promiseBPP, promiseMA, etc.

Marcos Villagra
fuente
Olvidé mencionar que esto es solo con respecto al PH, por supuesto, y parece ser un enfoque más plausible que tomar cualquier clase de complejidad.
Marcos Villagra
55
Enlace: mathoverflow.net/questions/9221/…
Ryan Williams
3
CsiPAGSPAGSMANC
sí, la enumeración de máquinas de clases semánticas no es recursiva. Pero las versiones prometedoras de las clases semánticas (promiseBPP, promiseMA, ...) son de hecho sintácticas.
Marcos Villagra