¿Por qué hay tan pocos candidatos naturales para el estado intermedio NP?

29

Es bien sabido por el teorema de Ladner que si , entonces existen infinitos problemas -intermediate ( ). También hay candidatos naturales para este estado, como Graph Isomorphism y varios otros, consulte Problemas entre P y NPC . Sin embargo, se sabe que la gran mayoría de la multitud de problemas conocidos de encuentran en o . Solo una pequeña fracción de ellos sigue siendo candidato para . En otras palabras, si elegimos al azar un N P naturalN P N P I natural N P P N P C N P IPNPNPNPInatural NPPNPCNPINP-problema entre los conocidos, tenemos muy pocas posibilidades de elegir un candidato NPI¿Hay alguna explicación para este fenómeno?

Podría pensar en 3 posibles explicaciones, más en el lado filosófico:

  1. La razón para tener una fracción tan pequeña de candidatos naturales para NPI es que NPI eventualmente resultará estar vacía. Lo sé, esto implica P=NP , por lo que es muy poco probable. Sin embargo, uno podría argumentar (aunque no soy uno de ellos) que la rareza de los problemas naturales de NPI es una observación empírica que parece apoyar P=NP , en contraste con la mayoría de las otras observaciones.

  2. La pequeñez de "natural- NPI " representa una especie de transición de fase aguda entre problemas fáciles y difíciles. Aparentemente, los problemas algorítmicos significativos y naturales se comportan de una manera que tienden a ser fáciles o difíciles, la transición es estrecha (pero aún existe).

  3. El argumento en 2 se puede llevar al extremo: eventualmente todos los problemas en "natural- NPI " se pondrán en PNPC , pero PNP , entonces NPI . Esto significaría que todos los problemas restantes en NPIson "antinaturales" (artificiales, sin sentido de la vida real). Una interpretación de esto podría ser que los problemas naturales son fáciles o difíciles; la transición es solo una construcción lógica, sin significado "físico". Esto recuerda un poco al caso de los números irracionales, que son perfectamente lógicos, pero no surgen como el valor medido de ninguna cantidad física. Como tales, no provienen de la realidad física, están más bien en el "cierre lógico" de esa realidad.

¿Qué explicación te gusta más o puedes sugerir otra?

Andras Farago
fuente
13
Um, la longitud de la diagonal de un cuadrado de 1 cm x 1 cm es un número irracional ...
Joshua Grochow
44
También puede resultarle interesante que, en la teoría de la medida limitada por recursos, la colección de conjuntos completos de NP tiene una medida p 0. En otras palabras, los conjuntos aleatorios p en NP no son completos de NP. De hecho, esto es cierto para cualquier grado polinómico de tiempo único. (La medida de la colección de todos los conjuntos de NP es una pregunta abierta: si no es cero o no se puede medir, entonces )PNP
Joshua Grochow
77
la respuesta tiene que ver principalmente con qué problemas encontramos "naturales", que es una pregunta bastante filosófica. Tampoco está del todo claro que la premisa de la pregunta sea válida: muchos problemas derivados de la criptografía tienen una complejidad intermedia. Finalmente, lo que estás diciendo sobre los números irracionales es absurdo.
Sasho Nikolov

Respuestas:

26

Como otros han señalado, es discutible hasta qué punto lo que estás tratando de explicar es incluso cierto. Se podría argumentar que, en los años 60 y 70, los científicos teóricos de la informática estaban más interesados en el tipo de problemas que resultan ser P o NP-completo. Hoy en día, debido al aumento de la criptografía teórica de la complejidad, la computación cuántica, las redes, etc., así como al simple hecho de que la integridad de NP se ha entendido tan bien, nos hemos interesado cada vez más en El tipo de problemas que resultan ser NP-intermedios.

Aún así, uno podría preguntarse: en la medida en que la cosa sea cierta, es decir, en la medida en que tantos problemas de búsqueda y optimización natural "se adapten" a ser NP-completos o bien en P --- en esa medida , ¿por qué es verdad? Aquí, creo que puede obtener mucha intuición al observar un fenómeno anterior de la computabilidad: que tantos modelos naturales de computación "encajan" en ser completos para Turing. En ese caso, diría que la explicación es que, una vez que tiene algunos componentes básicos, una memoria de lectura / escritura, bucles, condicionales, etc., es difícil de evitarser capaz de simular una máquina de Turing y, por lo tanto, ser Turing completo. De la misma manera, una vez que su problema de búsqueda u optimización tiene algunos componentes básicos, lo más importante, la capacidad de construir "gadgets" que imitan puertas lógicas como AND, OR y NOT --- es difícil evitar poder para codificar SAT y por lo tanto ser NP-completo.

De la forma en que me gusta pensarlo, los problemas como el SAT ejercen una poderosa "atracción gravitacional" sobre todos los demás problemas computacionales en su vecindad, lo que hace que quieran "recuperarse" para ser NP-completos también. Por lo tanto, normalmente ni siquiera requiere una explicación especial cuando otro problema sucumbe a ese tirón. Lo que es más llamativo y necesita más explicación es cuando un problema NP (aparentemente) difícil tiene alguna propiedad que le permite resistir la atracción gravitacional del SAT. Entonces queremos saber: ¿cuál es esa propiedad? ¿Por qué no puedes jugar el truco habitual de completar NP para este problema, de construir dispositivos que codifiquen puertas lógicas booleanas? Hice una lista de algunas respuestas comunes a esa pregunta en esta reciente respuesta de CS.SE, pero (como otro comentarista ya señaló) hay otras posibles respuestas que me perdí.

Scott Aaronson
fuente
También relevante para la última parte es la pregunta de Scott cstheory.stackexchange.com/questions/19256/…
András Salamon
17

Muchos problemas naturales pueden expresarse como problemas de satisfacción de restricciones, y existen teoremas de dicotomía para los CSP.

Joshua Grochow
fuente
9

Solo una broma: después de pensar en la "atracción gravitacional SAT" en la buena respuesta de Scott Aaronson, me vino a la mente otra metáfora: ¡el sándwich 3-SAT 2-SAT !

ingrese la descripción de la imagen aquí



... pero no sé si el sándwich puede llenarse con ingredientes naturales (sin embargo, descubrí que podría llenarse con algunos -SAT salsa [1] si la hipótesis del tiempo exponencial es verdadera) :-D(2+(logn)kn2)

Otro resultado en [1] es que no se puede llenar con .(2+1/n2ϵ),0<ϵ<2

[1] Yunlei Zhao, Xiaotie Deng, CH Lee, Hong Zhu, -SAT y sus propiedades(2+f(n)) , Matemática Aplicada Discreta, Volumen 136, Número 1, 30 de enero de 2004, Páginas 3-11, ISSN 0166 -218X.

Marzio De Biasi
fuente
3
Sin embargo, no se puede llenar con -SAT: eccc.hpi-web.de/report/2013/159(2+ε)
Joshua Grochow
@JoshuaGrochow: mi referencia para la "salsa" es el papel Zhao, Deng, Lee y Zhu " -SAT y sus propiedades" también demostraron que no se puede llenar con ( 2 +(2+f(n)) ... voy a dar un vistazo a la ( 2 + ε ) de papel -SAT (sólo abrió y es extraño que no pusieron Zhao et al trabajo. sus referencias)(2+1/n2ϵ),0<ϵ<2(2+ϵ)
Marzio De Biasi
3
Las definiciones de -SAT en los dos documentos son diferentes; Creo que ambos son correctos! (2+f(n))
Joshua Grochow
1
@MarzioDeBiasi, debería considerar agregar esas dos referencias directamente a su respuesta (donde se pueden buscar) en lugar de ocultarlas en los comentarios.
Artem Kaznatcheev
8

No podemos descartar una cuarta posibilidad de que haya un montón de N P natural NP intermedios. La aparente escasez se debe a la falta de técnicas y herramientas necesarias para probar el estado intermedio de bajo alguna conjetura de complejidad plausible (Arora y Barak notaron que no podemos probar el estado intermedio de N P de ningún problema natural de N P , incluso suponiendo que P N P ).NPNPNPPNP

Parece que las compuertas de los problemas intermedios naturales de están abiertas. Jonsson, Lagerkvist y Nordh extendieron la técnica de diagonalización de Ladner, conocida como hacer agujeros en los problemas , y la aplicaron a los problemas de satisfacción de restricciones. Obtuvieron un CSP que es candidato para el estado intermedio N P. Probaron que el problema de la abducción proposicional tiene fragmentos intermedios de N P.NPNPNP

Además, Grohe demostró la existencia de -problemas de CSP intermedios suponiendo que F P T W [ 1 ] . Obtuvo tales problemas al restringir el ancho del árbol de los gráficos primarios correspondientes.NPFPTW[1]

referencias :

1- M. Grohe. La complejidad del homomorfismo y los problemas de satisfacción de restricciones vistos desde el otro lado. Revista de la ACM, 54 (1), artículo 1, 2007

2- Peter Jonsson, Victor Lagerkvist y Gustav Nordh. Soplando agujeros en varios aspectos de problemas computacionales, con aplicaciones para restringir la satisfacción. En Actas de la XIX Conferencia Internacional sobre Principios y Práctica de la Programación de Restricciones (CP-2013). 2013

Mohammad Al-Turkistany
fuente
1
¿Por qué estos problemas de CSP no entran en la conjetura de la dicotomía?
Sasho Nikolov
1
¿Restringir el ancho del árbol como en el resultado de Grohe es realmente natural? (La pregunta no es retórica, honestamente no lo sé). En mi opinión, las construcciones Johnsson-Lagerkvsit-Nordh solo parecen un poco más naturales que las de Ladner. Creo que el punto en su primer párrafo es excelente.
Joshua Grochow
@ JoshuaGrochow Me temo que es discutible ya que no existe una noción formal de lo que significa natural .
Mohammad Al-Turkistany
@SashoNikolov ¿Te refieres a la conjetura de dicotomía de Feder y Vardi?
Mohammad Al-Turkistany
1
@ MohammadAl-Turkistany: No veo una contradicción. JLN construye explícitamente clases de instancias que no están en la forma CSP ( , _ ) o CSP ( _ , B ), por lo que evitan las dicotomías que se conocen. Ver también el par de documentos anteriores de Chen-Thurley-Weyer y Bodirsky-Grohe para ideas similares. A__B
András Salamon
7

Aquí hay un cuento de hadas sobre la estructura de Ricitos de Oro de los problemas NP-intermedios. (Advertencia: esta historia puede ser una falacia útil para generar y probar hipótesis potenciales, pero no pretende ser científicamente rigurosa. Se basa en una parte de la hipótesis del tiempo exponencial, una pizca de magia de complejidad de Kolmogorov, algunas piezas tomadas de la teoría del SAT resolver, y la tricotomía heurística de Terence Tao para problemas. Consumir bajo su propio riesgo, como con todos los brebajes sobre matemáticas matemáticos.

Si casi todas las instancias en un problema en NP están altamente estructuradas, entonces el problema está realmente en P. Las instancias, por lo tanto, casi todas contienen mucha redundancia, y un algoritmo de tiempo polinómico para el problema es una forma de factorizar la redundancia. Incluso es concebible que cada problema en P se pueda obtener tomando algún problema en EXP y agregando algo de redundancia estructurada, a través de alguna forma de relleno (no necesariamente del tipo habitual). Si esto fuera así, entonces un algoritmo de tiempo polinómico podría verse como una forma eficiente de deshacer ese relleno.

Si hay suficientes instancias que no están estructuradas, formando un "núcleo de dureza", entonces el problema es NP-completo.

Sin embargo, si este "núcleo de dureza" es demasiado escaso, entonces solo tiene espacio para representar algo de SAT, por lo que el problema está en P o NP-intermedio. (Este argumento es la esencia del teorema de Ladner). Para usar la analogía de Scott, el "núcleo de dureza" ejerce una atracción gravitacional sobre el problema, para que sea NP-completo. Las instancias en el "núcleo de dureza" no contienen mucha redundancia, y el único algoritmo realista que funciona para todas esas instancias es la búsqueda de fuerza bruta (por supuesto, si solo hay muchas, entonces la búsqueda en la tabla también funciona).

Desde esta perspectiva, los problemas NP-intermedios deberían ser raros en la práctica, ya que requieren un buen equilibrio de Ricitos de Oro entre instancias estructuradas y no estructuradas. Las instancias deben tener suficiente redundancia para que sean parcialmente susceptibles a un algoritmo, pero debe haber suficiente núcleo de dureza para que el problema no esté en P.


Uno puede contar una historia aún más simple (y divertida, pero también potencialmente más engañosa) basada en acertijos. Con solo unas pocas restricciones, se puede forzar una gran cantidad de búsquedas, por ejemplo, NxN Sudoku es NP-complete. Ahora considere pedirle que resuelva muchos rompecabezas pequeños como una sola instancia, de una sola vez (por ejemplo, muchos Sudokus 9x9). El tiempo necesario será aproximadamente lineal en el número de acertijos en cada caso, y este problema está en P. Para problemas intermedios, uno puede pensar que cada caso es un número grande (pero no demasiado grande) de Sudokus en grande. (pero no demasiado grandes) rejillas. ¡La razón por la que no observamos muchos de estos problemas es porque sería triste plantearlos y resolverlos!

András Salamon
fuente
1
LCLknk+kCLPL) plantean la hipótesis de que los lenguajes en NP con núcleos suficientemente densos deben ser NP-completos.
Joshua Grochow
1
Las referencias que Joshua mencionó: Lynch: dx.doi.org/10.1145/321892.321895 y Orponen-Schöning: dx.doi.org/10.1016/S0019-9958(86)80024-9 también ver Orponen-Ko-Schöning-Watanabe: dx. doi.org/10.1145/174644.174648
András Salamon
2

NPINPINP

nlognNPI NPxQxQNPIP

NPINPNPINPC

NPIP

Andras Farago
fuente
3
W[1]
xQxO(log|x|)
Para 3-COLORING, ¿cuál es la versión reducida del problema?
András Salamon
1
nlogn
2
No es la diferencia b / w "ser una camarilla" y "ser de 3 colores". Es la diferencia entre el problema original que es: 1) ¿un gráfico tiene una subgrafía con alguna propiedad de un tamaño dado (por ejemplo, CLIQUE) vs. 2) si un gráfico tiene una propiedad. En el caso de (1), cambiar el tamaño para que sea log es natural, b / c el tamaño del subgrafo ya era parte de la pregunta. Cuando haces tu truco con (2), agregas el tamaño del subgráfico como una nueva parte del problema.
Joshua Grochow