Probar límites inferiores probando límites superiores

29

El reciente resultado innovador del límite inferior de la complejidad del circuito de Ryan Williams proporciona una técnica de prueba que utiliza el resultado del límite superior para demostrar la complejidad de los límites inferiores. Suresh Venkat en su respuesta a esta pregunta, ¿hay resultados contraintuitivos en informática teórica? , proporcionó dos ejemplos de establecer límites inferiores probando los límites superiores.

  • ¿Cuáles son los otros resultados interesantes para probar los límites inferiores de la complejidad que se obtuvieron al probar los límites superiores de la complejidad?

  • ¿Hay alguna conjetura de límite superior que implicaría (o P \ ne NP )?NPP/polyPNP

Mohammad Al-Turkistany
fuente
¿Debería ser esto un CW?
Mohammad Al-Turkistany
Me gusta como es (no CW), pero creo que es un [soft-question].
MS Dousti
2
@Sadeq: no piense que esta es una pregunta fácil, es lo suficientemente precisa como para tener una respuesta clara.
Kaveh
El resultado de Meyer señalado por Suresh muestra que la existencia de circuitos polinómicos para EXP probaría PNP .
Mohammad Al-Turkistany

Respuestas:

23

Uno podría cambiar la pregunta y preguntar qué límites inferiores no se prueban demostrando un límite superior. Casi todos los límites inferiores de la complejidad de la comunicación (y el límite inferior del algoritmo de transmisión y los límites inferiores de la estructura de datos que dependen de los argumentos de la complejidad de la comunicación) se demuestran demostrando que un protocolo de comunicación puede convertirse constructivamente en un esquema de codificación, con la longitud de la codificación dependiendo de La complejidad de la comunicación del protocolo, y el límite inferior para el protocolo se deriva del hecho de que no puede codificar todos los mensajes de n bits con n-1 bits o menos.

Los límites inferiores del circuito Razborov-Smolensky funcionan al mostrar cómo simular circuitos de profundidad limitada mediante polinomios de bajo grado.

Un par de candidatos de límites inferiores que no se prueban con un límite superior podría ser el teorema de la jerarquía de tiempo (aunque, para obtener los límites más ajustados, se necesita una máquina de turing universal eficiente, que es una tarea algorítmica no trivial) y la prueba de los límites inferiores de AC0 utilizando el lema de conmutación (pero la prueba más clara del lema de conmutación utiliza un conteo / incompresibilidad / complejidad de Kolmogorov)

Luca Trevisan
fuente
1
Interesante, ¡ese es un gran resumen de la complejidad de la comunicación en los límites inferiores! Otro candidato (¿extraño?): El teorema / diagonalización de Ladner. Los límites, por supuesto, no se especifican (¡ni siquiera los problemas!), Pero muestra un límite inferior superpolinómico para algún problema. Por supuesto, esto supone P NP, que posiblemente podría probarse con un límite superior, a la GCT ...
Daniel Apon
14

De una manera extraña, el teorema de PCP en sí mismo es un buen ejemplo de probar un límite inferior a través de un límite superior. Una estrategia aleatoria "eficiente" para verificar una prueba usando un número constante de sondas de la prueba y solo bits aleatorios conduce a un límite inferior para aproximar el número de cláusulas satisfechas en una instancia de 3SAT.logn

Suresh Venkat
fuente
10
Si cuenta la dureza NP (en oposición a la separación de una clase) como límites inferiores, no necesita el teorema de PCP; Las reducciones son algoritmos eficientes que prueban que algunos problemas son difíciles.
Tsuyoshi Ito
Ese es un buen punto, Tsuyoshi. Sin embargo, las reducciones de dureza NP son "directas". Demuestre que resolver un problema desconocido resuelve un problema difícil conocido. Algunos de los ejemplos dados aquí son más indirectos. Pero esto es subjetivo, por supuesto.
Suresh Venkat
3
La misma afirmación del teorema de PCP es la completitud NP de Gap-3SAT. Además, no sé a qué te referías al afirmar que el teorema de PCP es indirecto. Es cierto que el teorema de PCP requiere una de las pruebas más complicadas entre los resultados de completitud NP, pero ¿es algo bueno?
Tsuyoshi Ito
Suresh, ¿podría publicar aquí, como una nueva respuesta, una versión ampliada de los dos ejemplos a los que hizo referencia en su respuesta a la otra pregunta (resultado de Meyer y GCT)?
Mohammad Al-Turkistany
alguna razón por qué? No tengo problemas para hacerlo, pero ¿es necesario ya que lo mencionas en la pregunta?
Suresh Venkat
12

El método de incompresibilidad es un método basado en la complejidad de Kolmogorov para probar límites inferiores. Una de las primeras aplicaciones de este método fue demostrar que reconocer palíndromos en una máquina Turing con una sola cinta requiere tiempo cuadrático.

Hablando en términos generales, la idea de este método es describir un procedimiento para encontrar una entrada utilizando la información contenida en la ejecución de un algoritmo que resuelve el problema que consideramos en esta entrada. Cuanto mejor sea el procedimiento, mayor será el límite inferior del problema original.

Por supuesto, todos los detalles se pueden encontrar en el libro de texto de Li y Vitanyi .

Bagazo
fuente
11

Para la pregunta "límite inferior a través del límite superior", usted hizo:

El documento de STOC 2010 "Cómo comprimir la comunicación interactiva" [BBCR10] llega a un teorema de suma directa mejorado para la complejidad de la comunicación aleatoria al demostrar un protocolo de compresión mejorado para la comunicación interactiva.

Específicamente, dado que dos partes calculan alguna función conjunta de sus entradas mutuas (es decir, un escenario de cómputo interactivo), muestran que cualquier protocolo que comunica bits y revela bits de nueva información a las partes involucradas puede simularse mediante un nuevo protocolo usando bits: el límite superior mejorado.I ˜ O ( CIO~(CI)

Como consecuencia de esta compresión mejorada del protocolo, muestran que, en el peor de los casos: Dada cualquier función que requiera tiempo para calcular individualmente, calcular copias de requiere al menos tiempo - la mejora límite inferior.n k f fnkfkn

Daniel Apon
fuente
7

Esto es de alguna manera diferente de lo que pediste, pero como está relacionado, pensé que podría mencionarlo.

Carter y Wegman (1977) introdujeron la noción de hashing universal . La noción se usó en numerosos artículos ( Sipser (1983) , Stockmeyer (1983) , Babai (1985) y Goldwasser & Sipser (1986) ) para probar límites inferiores aproximados .

Esto fue hasta 1987, en que Fortnow hizo uso del hashing universal para probar los límites superiores aproximados . (De hecho, para proporcionar un protocolo para probar los límites superiores aproximados).


Editar:

Estos no son resultados de límite inferior, pero podrían ser útiles de todos modos:

NPP/polyPH=Σ2p=Π2p

NPP/polyAM=MA

coNPNP/polyPH=Σ3p=Π3p

MS Dousti
fuente
5

PNP

CC1Cm

PNP

Mohammad Al-Turkistany
fuente
5

Aquí hay un ejemplo de Complejidad computacional: un enfoque moderno de Arora y Barak (página 128):

EXPo(2n/n)PNP

Mohammad Al-Turkistany
fuente