¿Podría haber un subconjunto oculto extremadamente grande de problemas polinómicamente solucionables dentro de problemas NP-completos?

9

Supongamos que P! = NP.

Sabemos que podemos hacer instancias fáciles de 3-SAT en cualquier momento. También podemos generar lo que creemos que son instancias difíciles (porque nuestros algoritmos no pueden resolverlas rápidamente). ¿Hay algo que impida que el conjunto de instancias difíciles sea arbitrariamente pequeño, siempre que para cualquier tamaño de instancia dado (n) solo haya instancias Poly (n) (o incluso constantes) de tamaño Poly (n) o menor?

Para cualquier instancia de 3-SAT difícil, tendríamos que agregar el conjunto de todas las instancias de 3-SAT que reduce a través del bucle a través del ciclo de reducción de NP-Completeness, pero no preveo que esto agregue mucho al número de instancias difíciles .

En este mundo, podríamos construir un algoritmo que resuelva polinómicamente todos los problemas completos de NP, excepto algunos excepcionales.

Editar: Una variante más suave de la pregunta: incluso si mostramos P! = NP, ¿cómo podríamos saber si un método dado para generar problemas de tamaño n 3-SAT realmente generó uno difícil con alguna probabilidad requerida? Si no hay manera de saber solo de P! = NP, ¿qué se requiere para demostrar que podemos generar un problema difícil de NP completo?

Elliot JJ
fuente
44
Si. Los problemas de NP completo son difíciles en el peor de los casos. Es posible que la mayoría de las instancias de un problema de NP completo se puedan resolver de manera eficiente. Sin embargo, Russell Impagliazzo propuso un mundo (Pessiland) donde existen problemas de NP completo de caso promedio pero no existen funciones unidireccionales. En este mundo, no podemos generar instancias difíciles de un problema NP-completo con una solución conocida.
Mohammad Al-Turkistany
55
Si el conjunto de instancias duras de cada longitud es polinomialmente pequeño, entonces NP está contenido en P / poli. También hay otras formas de ver esto, buscar HeurP.
Kaveh
2
Esta pregunta parece abordar su edición: podemos (determinísticamente) generar instancias difíciles de SAT si y solo si unary unary . PNPP
usul
1
@ SarielHar-Peled En particular, NP P / poly colapsa PH al segundo nivel, lo que es consistente con P! = NP.
Suresh Venkat
2
No hay una forma conocida de conectar la dureza de NP en el peor de los casos y el promedio. Sin embargo, hay formas de conectar la dureza de caso promedio "leve" con la dureza de caso promedio "fuerte". Mi tesis es un punto de partida para ambos. ccs.neu.edu/home/viola/papers/thesis.pdf
Manu

Respuestas:

12

1) Dependiendo exactamente de lo que se quiso decir, la conclusión en la observación de Kaveh puede fortalecerse de a , esencialmente usando el Teorema de Mahaney. Es decir, si hay un algoritmo que resuelve SAT y se ejecuta en tiempo en todas las instancias de longitud excepto posiblemente tales instancias, donde y son polinomios, entonces de hecho . Ver, por ejemplo, Meyer y Paterson y las referencias allí, o la monografía de Schoning "Complejidad y estructura"P = N Pp ( n ) n q ( n ) p q P = N P p o l y ( n ) n PN PNPP/polyP=NPp(n)nq(n)pqP=NP. Entonces, si esto captura su noción de "instancias difíciles", entonces debe haber más de muchas instancias difíciles para cada , suponiendo .poly(n)nPNP

Para su información, estos algoritmos a veces se denominan algoritmos "apt" o "APT", por "tiempo casi polinómico" (no debe confundirse con la clase de complejidad más moderna , que es igual a )B P PalmostPBPP

2) Lo anterior se puede fortalecer aún más, como sigue. Suponga . Luego, lo anterior dice que para cualquier algoritmo que resuelva SAT y cualquier polinomio , hay un conjunto de instancias de tamaño superpolinomial en el que el algoritmo tarda más de tiempo. Pero el conjunto puede depender del algoritmo. p p ( n )PNPpp(n)

El resultado más fuerte cambia los cuantificadores y concluye: hay un conjunto de tamaños superpolinomiales H (para "duro") de tal manera que para cualquier algoritmo A que resuelve SAT y cualquier polinomio p, A lleva más de tiempo en todos, pero finitamente muchos elementos de H. Tal H se llama núcleo de complejidad (la suposición de tamaño no es parte de la definición de núcleo de complejidad). Lynch dio la definición y existencia de núcleos de complejidad . Orponen y Schoning prueban el resultado que acabo de citar .p(n)

Joshua Grochow
fuente
-3

otro ángulo sobre esta pregunta (fuera de la referencia al teorema de Mahaney). El "punto de transición" en SAT es un estudio de este fenómeno de distribución de instancias fáciles vs difíciles, especialmente en torno a un "punto crítico" donde la probabilidad de instancias difíciles se maximiza. La literatura sobre el tema es larga y compleja. Tiene enfoques empíricos y analíticos. tiene vínculos profundos con la física / termodinámica. [3] desafortunadamente, actualmente no hay una entrada de Wikipedia sobre este tema de teoría de complejidad muy significativo y fundamental. Además, no parece haber muchas encuestas generales o "estándar" sobre el tema. Aquí hay una referencia reciente para comenzar en las transiciones de fase SAT [1] y TCS en general. [4] su pregunta también cae en una categoría de "=?

¿Hay algo que impida que el conjunto de instancias difíciles sea arbitrariamente pequeño, siempre que para cualquier tamaño de instancia dado (n) solo haya instancias Poly (n) (o incluso constantes) de tamaño Poly (n) o menor?

de nuevo, el teorema de Mahaney (redactado de una manera ligeramente diferente) responde esto directamente. Otra forma de ver esto es que los intentos de reducir la distribución de instancias de alguna manera clave / característica conduce a funciones NP-completas. Un ejemplo de esto de la complejidad del circuito monótono es "funciones de corte". [2]

[1] Predicción de la satisfacción en la transición de fase Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

[2] Paul ES Dunne: La complejidad de las funciones de corte central. Theor Comput Sci. 44: 247-257 (1986)

[3] Solución analítica y algorítmica de problemas de satisfacción aleatorios M. Mezard, G. Parisi, R. Zecchina

[4] Transiciones de fase en problemas NP-completos: un desafío para la probabilidad, la combinatoria y la informática por Moore

vzn
fuente