¿Hay alguna explicación para la dificultad de probar límites inferiores cuadráticos para problemas NP interesantes?

11

Este es un seguimiento de mi pregunta anterior:

Mejor complejidad de tiempo determinista conocida límite inferior para un problema natural en NP

Me resulta desconcertante que no hayamos podido probar ningún límite inferior de tiempo determinista cuadrático para ningún problema interesante de NP que a la gente le interese e intente diseñar mejores algoritmos. Nuestra conjetura de hipótesis de tiempo exponencial establece que SAT no se puede resolver en tiempo determinista subexponencial, ¡pero ni siquiera podemos probar que SAT (o cualquier otro problema NP interesante) requiere tiempo cuadrático!

Sé que interesante es algo subjetivo y vago. No tengo una definicion. Pero permítanme tratar de describir lo que considero un problema interesante: estoy hablando de problemas que más de unas pocas personas encuentran interesantes. No estoy hablando de problemas aislados diseñados principalmente para responder alguna pregunta teórica. Si las personas no están tratando de encontrar algoritmos más rápidos para un problema, entonces es una indicación de que el problema no es tan interesante. Si desea ejemplos concretos de problemas interesantes, considere los problemas en el artículo de Karp de 1972 o en Garey y Johnson 1979 (la mayoría de ellos).

¿Hay alguna explicación de por qué no hemos podido probar ningún límite inferior determinístico cuadrático para ningún problema NP interesante?

cc.complexity-theory lower-bounds big-picture barriers Anónimo
fuente
3
¿Porque los límites inferiores son difíciles? ¿Qué tipo de explicación te satisfaría?
Jeffε
3
@ Jɛ ff E ¿qué tal explicaciones no triviales que son informativas y perspicaces? Intuiciones o resultados que explican por qué estamos atrapados donde estamos probando límites inferiores. Dado que nuestras afirmaciones han sido mucho más fuertes que nuestros resultados, estoy seguro de que otros expertos han pensado por qué después de décadas de intentarlo no hemos podido obtener un límite inferior cuadrático en un interesante problema de NP.
Anónimo
3
Aquí hay una explicación del blog de Lipton; Cebo y Switch: ¿Por qué los límites inferiores son tan difíciles? rjlipton.wordpress.com/2009/02/12/…
Mohammad Al-Turkistany
3
n2
2
La cuestión de los límites inferiores del tiempo cuadrático es relevante cuando restringe los algoritmos para que tengan muy poco espacio (por ejemplo, polylog), o cuando mira máquinas de Turing de una cinta (que tienen un acceso muy restringido a la memoria). Pero cuando la memoria no está restringida, y el acceso a la memoria no está restringido, la pregunta "real" es si hay límites inferiores de tiempo super-lineales para problemas NP interesantes, en cualquier modelo computacional de acceso aleatorio. (Grandjean demostró algunos límites inferiores súper lineales para máquinas Turing de múltiples cintas, pero dependen de la estructura de las cintas unidimensionales)
Ryan Williams,

Respuestas:

5

Aquí hay una explicación del blog de Lipton: Bait and Switch: ¿Por qué son tan difíciles los límites inferiores?

n2

La visión de Rudich explica por qué cualquier prueba de límite inferior de que se basa en el siguiente método no puede funcionar.

ff

Básicamente, no hay medida de progreso que pueda sobrevivir al truco de Bait and Switch de Rudich y que conduzca con éxito a un límite inferior.

Mohammad Al-Turkistany
fuente
4

Puede encontrar otra vista del argumento de "cebo y cambio" en el capítulo de pruebas naturales de Arora-Barak. Usan el mismo argumento para argumentar que un argumento de límite inferior de estilo "medida de complejidad formal" debe aplicarse a funciones aleatorias con alta probabilidad. Pero si una medida formal de complejidad

  1. asigna alta complejidad a una función aleatoria
  2. no asigna alta complejidad a una función fácil
  3. se puede calcular fácilmente a partir de la tabla de verdad de una función

entonces puede usarse para romper generadores pseudoaleatorios. Esta es la barrera de las pruebas naturales, informalmente. Argumentamos que 1. es muy razonable para muchos enfoques de límites inferiores, sin 2. la medida de complejidad parece inútil, y 3. se basa en la observación de que hemos podido convertir la mayoría de las pruebas de existencia combinatorias en algoritmos eficientes, y en intuición de que una prueba inherentemente no constructiva es difícil de idear.

CC′C′C

Sasho Nikolov
fuente