Problemas entre P y NPC

128

La factorización y el isomorfismo gráfico son problemas en NP que no se sabe que están en P ni en NP-Completo. ¿Cuáles son algunos otros problemas naturales (suficientemente diferentes) que comparten esta propiedad? Los ejemplos artificiales que provienen directamente de la prueba del teorema de Ladner no cuentan.

¿Alguno de estos ejemplos es probablemente NP-intermedio, suponiendo solo alguna hipótesis "razonable"?

Lev Reyzin
fuente
Aquí hay una pregunta similar que puede ser útil: cstheory.stackexchange.com/questions/52/…
Daniel Apon el
1
Pregunta relacionada en MO, con varios punteros específicamente para problemas en NP y co-NP pero no se sabe que están en P: mathoverflow.net/questions/31821/…
András Salamon
1
Hay varias clases de complejidad entre P y NP-complete que actualmente se consideran interesantes: PPAD, problemas que son equivalentes a UGC, NP co-NP, BPP, ... Si está solicitando una lista grande, podría haces esto un wiki de la comunidad por favor?
András Salamon
Gracias. Soy consciente del teorema de Ladner. Supongo que estaba pidiendo "problemas naturales". Supongo que PPAD tiene Nash Equilibria, así que eso cuenta ...
Lev Reyzin

Respuestas:

105

Aquí hay una colección de algunas de las respuestas de problemas entre P y NPC:

Lev Reyzin
fuente
55
Sí, este procedimiento funciona, como la respuesta "oficial".
Suresh Venkat
12
Sería genial poder agregar una respuesta a la lista de observación. Esto definitivamente sería mío.
András Salamon
99
Estoy eliminando Planar MAX 2-SAT de la lista, Guibas et al. en "Aproximación de polígonos y subdivisiones con rutas de enlace mínimas" ( springerlink.com/content/y234m35416w043v1 )
Bob Fraser
77
¿ Alguno de estos ejemplos es probablemente NP-intermedio, suponiendo solo alguna hipótesis "razonable" (es decir, una hipótesis menos trivial que "este problema es NP-intermedio")? Si es así, sería interesante mencionar eso en esta lista.
Timothy Chow
3
@Timothy Chow: el ejemplo anterior suponiendo que es demostrablemente intermedio, es decir, suponiendo que N E X P E X P , la versión acolchada de un problema completo de N E X P probablemente no sea - completado por Mahaney ni en , ya que eso contradeciría . NEXPEXPNEXPEXPNEXPP N E X P E X PNPPNEXPEXP
Joshua Grochow
45

Mi problema favorito en esta clase (lo expresaré como un problema funcional, pero es fácil convertirlo en un problema de decisión de la manera estándar): calcule la distancia de rotación entre dos árboles binarios (equivalentemente, la distancia de giro entre dos triangulaciones de Un polígono convexo).

David Eppstein
fuente
1
Ese es un problema claro: no me di cuenta de que estaba en el limbo.
Suresh Venkat
3
Sí, yo tampoco lo sabía! Para todos estos problemas / respuestas, me pregunto si están en el Limbo porque creemos que realmente lo están o si son más como PRIMES ...
Lev Reyzin
Este problema y su estado potencialmente intermedio deberían ser más conocidos. ¿Me puede dar una referencia? Además, ¿hay algún resultado que indique que no está NP completo, como lo hay para el isomorfismo gráfico y los problemas relacionados?
Joshua Grochow
8
Una referencia muy bonita e importante pero más antigua es Thurston, Sleator y Tarjan, "Distancia de rotación, triangulaciones y geometría hiperbólica", STOC'86 y JAMS'88. Para una referencia reciente que menciona explícitamente la complejidad del problema como aún abierta, ver Lucas, "Un tamaño de kernel mejorado para la distancia de rotación en árboles binarios", IPL 2010, dx.doi.org/10.1016/j.ipl.2010.04. 022
David Eppstein
1
Interesante. Al parecer, explorar el espacio de rotación también es un área activa de investigación. "El gráfico de rotación de los árboles k-ary es hamiltoniano", IPL 2008, dx.doi.org/10.1016/j.ipl.2008.09.013
Chad Brewbaker
38

Un problema que no se menciona ni en esta lista ni en la lista MO es el problema de la autopista de peaje. Dado un conjunto múltiple de n (n-1) / 2 números, cada número que representa la distancia entre dos puntos en la línea, reconstruye las posiciones de los puntos originales.

Tenga en cuenta que lo que hace que esto no sea trivial es que para un número dado d en el conjunto múltiple, no sabe qué par de puntos están separados por unidades d.

Si bien se sabe que para cualquier caso solo hay un número polinómico de soluciones, ¡no se sabe cómo encontrar una!

Suresh Venkat
fuente
Gracias, esta es buena. Me recuerda algunos otros problemas de "localización". ¿Se cree realmente que no está en p?
Lev Reyzin
No soy consciente de que la autopista de peaje esté directamente relacionada con problemas conocidos en complejidad. Sin embargo, existe una relación de "dirección equivocada" con la factorización, ya que el problema de la autopista de peaje puede expresarse como un problema de factorización en un polinomio elegido adecuadamente.
Suresh Venkat
1
¿Se conocen consecuencias poco probables de que este problema sea NP completo, como las hay para el isomorfismo gráfico (colapso de PH)?
Joshua Grochow
no que yo supiese. no se ha estudiado mucho, lo cual es una pena, porque es muy natural.
Suresh Venkat
2
Te encuentras con un problema similar en bioinformática: dado un conjunto de subcadenas potencialmente / con suerte superpuestas, creadas al azar de una cadena mucho más larga que las piezas individuales; calcular la cadena original (secuenciación genética)
Raphael
38

El problema de las sumas de raíces cuadradas: Dadas dos secuencias y b 1 , b 2 , ... , b n de enteros positivos, es A : = i a1,a2,,anb1,b2,,bn menor que, igual o mayor queB:=iA:=iai ?B:=ibi

  • El problema tiene un algoritmo trivial de tiempo en la RAM real. ¡Solo calcule las sumas y compárelas! Pero esto no implica pertenencia a P.O(n)

  • Existe un algoritmo obvio de precisión finita, pero no se sabe si un número polinómico de bits de precisión es suficiente para la corrección. (Ver http://maven.smith.edu/~orourke/TOPP/P33.html para más detalles).

  • El teorema de Pythogorean implica que la longitud de cualquier curva poligonal cuyos vértices y puntos finales enteros es una suma de raíces cuadradas de enteros. Por lo tanto, el problema de la suma de raíces es inherente a varios problemas de geometría computacional plana, incluidos los árboles de expansión mínima euclidiana , los caminos más cortos euclidianos , las triangulaciones de peso mínimo y el problema del vendedor ambulante euclidiano . (El problema Euclidean MST se puede resolver en tiempo polinomial sin resolver el problema de la suma de raíces, gracias a la estructura matroide subyacente y al hecho de que el EMST es un subgráfico de la triangulación de Delaunay).

  • No es un algoritmo aleatorio en tiempo polinómico, debido a Johannes Blömer , para decidir si las dos sumas son iguales. Sin embargo, si la respuesta es no, el algoritmo de Blömer no determina qué suma es mayor.

  • La versión de decisión de este problema (¿ ?) Ni siquiera se sabe que está en NP. Sin embargo, el algoritmo de Blömer implica que si el problema de decisión está en NP, entonces también está en co-NP. Por lo tanto, es poco probable que el problema sea NP-completo.A>B

Jeffε
fuente
3
Una linda, me gusta !!
Hsien-Chih Chang 張顯 之
Bueno, si tomamos solo 1000 enteros aleatorios, no demasiado grandes, entonces hay alrededor de formas de dividirlos en dos conjuntos, por lo que esperaría que dos de estas sumas estén dentro de 900 o más bits entre sí (y dentro de la mitad de la suma total). Por otro lado, encontrar las "peores" dos secuencias para comparar entre estas 2 999 posibilidades también es muy, muy difícil. 29992999
gnasher729
30

Aquí hay una lista de problemas que pueden o no calificar como "suficientemente" diferentes. Por la misma prueba que para el isomorfismo gráfico, si alguno de ellos tiene NP completo, entonces la Jerarquía polinómica se colapsa al segundo nivel. No creo que haya un amplio consenso sobre cuál de estos "debería" estar en P.

  • Automorfismo de gráficos (determine si un gráfico tiene un automorfismo no trivial). Se reduce al isomorfismo gráfico, pero no se sabe (¿no se piensa?) Que sea GI-hard.
  • Isomorfismo de grupo y Automorfismo (donde los grupos están dados por sus tablas de multiplicar). Nuevamente, se reduce al isomorfismo gráfico, pero no se cree que sea GI-hard.
  • Anillo isomorfismo y automorfismo. En cierto sentido, este es el abuelo de todos los problemas anteriores, ya que la factorización de enteros es equivalente a encontrar un automorfismo no trivial de un anillo, y el isomorfismo gráfico se reduce a isomorfismo de anillo. Ver Neeraj Kayal, Nitin Saxena. Complejidad de los problemas del anillo de morfismo. Complejidad computacional 15 (4): 342-390 (2006). (Curiosamente, determinar si un anillo tiene un automorfismo no trivial está en ).P
  • Esta publicación de Bill Gasarch contiene algunos otros problemas con el sabor de la teoría de Ramsey que parecen ser intermedios.
  • Según el teorema de Mahaney, ningún conjunto disperso puede ser NP-completo. Pero también sabemos que hay conjuntos dispersos en - P si y sólo si N E X P no es igual a E X P . Asumiendo N E X P E X P , la versión acolchada de cualquier problema completo de N E X P es de complejidad intermedia. (Tal conjunto no puede estar en P a menos que N E X P = E X PNPPNEXPEXPNEXPEXPNEXPPNEXP=EXP, contradiciendo nuestra suposición.) Hay muchos problemas naturales completos de NEXP
Joshua Grochow
fuente
Me gusta el ultimo ejemplo. ¿Tienes alguna referencia al respecto?
Marcos Villagra
1
SR Mahaney. Conjuntos completos dispersos para NP: solución de una conjetura de Berman y Hartmanis. Revista de Informática y Ciencias del Sistema 25: 130-143. 1982. dx.doi.org/10.1016/0022-0000(82)90002-2 Conjuntos dispersos en NP - P iff NEXP neq EXP: J. Hartmanis, N. Immerman, V. Sewelson, Conjuntos dispersos en NP-P: EXPTIME versus NEXPTIME, Information and Control, Volume 65, Issues 2-3, May-June 1985, Páginas 158-181. dx.doi.org/10.1016/S0019-9958(85)80004-8
Joshua Grochow
Esta es una buena lista, aunque las tres primeras son bastante similares :) Me gusta el último ejemplo también.
Lev Reyzin
28

El problema del tamaño mínimo del circuito (MCSP) es mi problema "natural" favorito en NP que no se conoce como NP completo: dada la tabla de verdad (de tamaño n = 2 ^ m) de una función booleana con variante m f, y dado un número s, ¿tiene f un circuito de tamaño s? Si MCSP es fácil, entonces no existe una función unidireccional criptográficamente segura. Este problema y sus variantes proporcionaron gran parte de la motivación para el estudio de los algoritmos de "fuerza bruta" en Rusia, lo que llevó al trabajo de Levin sobre la integridad de NP. Este problema también se puede ver en términos de complejidad de Kolmogorov limitada por recursos: preguntando si una cadena se puede recuperar rápidamente de una breve descripción. Esta versión del problema fue estudiada por Ko; el nombre MCSP fue usado primero por Cai y Kabanets, que yo sepa. Se pueden encontrar más referencias en algunos documentos míos: http://ftp.cs.rutgers.edu/pub/allender/KT.pdf http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf

Eric Allender
fuente
24

Auto dualidad monótona

Para cualquier boolean función f=f(x1,x2,...,xn) , que es dual es fd=f¯(x1¯,x2¯,...,xn¯) . Dada f(x1,x2,...,xn)representado por una fórmula CNF, tenemos que decidir si f=fd .

Este problema está en co-NP [ log2n ], es decir, es decidible con O(log2n/loglogn) pasos no deterministas. Por lo tanto, tiene un algoritmo de tiempo cuasi-polinomial (tiempo O(nlogn/loglogn) ) y, por lo tanto, es poco probable que sea co-NP-hard.

Todavía está abierto si este problema está en P o no. Se pueden encontrar más detalles en el documento de 2008 " Aspectos computacionales de la dualización monótona: una breve encuesta " de Thomas Eiter, Kazuhisa Makino y Georg Gottlob.

Danu
fuente
23

Trivialidad del nudo: Dada una cadena poligonal cerrada en 3 espacios, ¿está anudada (es decir, isotópica ambiental a un círculo plano)?

Se sabe que esto está en NP por resultados profundos en la teoría de la superficie normal, pero no se conoce un algoritmo de poli-tiempo o prueba de dureza NP.

Jeffε
fuente
1
Vale la pena mencionar que, como con muchos problemas potencialmente NP-intermedios, se sabe que una ligera variante es NP-completa. A saber, el género de nudo de 3 múltiples es NP-completo: dada una cadena poligonal cerrada en un múltiple de 3 triangulados y un entero g, ¿es el nudo el límite de una superficie de género como máximo g? (Ser el nudo es equivalente al género 0.) doi.acm.org.proxy.uchicago.edu/10.1145/509907.510016
Joshua Grochow
También está contenido en co-AM (Hara, Tani, Yamamoto), por lo que no es NPC a menos que la jerarquía polinómica se colapse.
Peter Shor
3
En realidad, eso todavía está abierto. Tasos Sidiropoulos encontró un error en la prueba Hara-Tani-Yamamoto.
Jeffε
Desde el momento en que esta respuesta fue publicada primero, Kuperberg coloca en condicionada a la Generalizado hipótesis de Riemann, y Lackenby coloca que unconditonally en c o N P . coNPcoNP
Mark S
19

No se sabe si es posible decidir en tiempo polinómico si el jugador 1 tiene una estrategia ganadora en un juego de paridad (desde una posición inicial dada). Sin embargo, el problema está contenido en NP y co-NP e incluso en UP y co-UP.

Matías
fuente
¿Puedes dar una referencia? Suena interesante.
Joshua Grochow
1
M. Jurdzinski. Decidir al ganador en Parity Games está en UP \ cap co-Up. Cartas de procesamiento de información 68 (3): 119-124. 1998. Al menos debería ser un buen punto de partida.
Matthias
El reciente artículo "Un algoritmo de bombeo para juegos eróticos de rentabilidad media estocástica con información perfecta" también muestra que incluso una generalización del juego de paridad se puede resolver en tiempo pseudo-polinomial. En particular, muestran que un juego llamado juego BWR tiene un algoritmo de tiempo pseudo-polinomial cuando hay un número constante de "nodos aleatorios". El juego de paridad es el caso donde no hay nodos aleatorios.
Danu
Recientemente se demostró que los juegos de paridad se pueden resolver en tiempo cuasipolinomial, ver aquí, por ejemplo.
Thomas Klimpel
18

Obtiene una lista muy larga de problemas si está dispuesto a aceptar problemas de aproximación, como aproximar Max-Cut a un factor de 0.878. No sabemos si es NP-hard o en P (solo sabemos NP-hardness suponiendo la conjetura de Uniuqe Games).

Moritz
fuente
Sí, ese fue un comentario tonto que comencé a eliminar tan pronto como se publicó. Gracias. :)
Daniel Apon
¡Gracias! Pero supongo que no estaba pensando tanto en los problemas de aproximación, sino más bien en los problemas naturales.
Lev Reyzin
Podría decirse que estos son problemas naturales, ya que corresponden a lo que se puede lograr mediante un conjunto natural de técnicas, en este caso, la programación semidefinida.
Moritz
Supongo que "natural" es un criterio vago ...
Lev Reyzin
18

En una fórmula CNF monótona , cada cláusula contiene solo literales positivos o solo negativos. En una fórmula CNF monótona que se cruza, cada cláusula positiva tiene alguna variable en común con cada cláusula negativa.

El problema de decisión

SAT MONOTONO INTERSECTANTE
Entrada: fórmula CNF monótona de intersección Pregunta: ¿ f es satisfactoria?f
f

tiene un algoritmo que se remonta a 1996, pero no se sabe que esté en P. (Por supuesto, podría estar en P, pero ese sería un resultado importante).no(log n)

  • Thomas Eiter y Georg Gottlob, Computación Transversal Hipergráfica y Problemas Relacionados en Lógica e IA , JELIA 2002. doi: 10.1007 / 3-540-45757-7_53
András Salamon
fuente
17

La versión Pigeonhole de Subset Sum (o Subset Sum Equality).

Dado:

n - 1 k = 0 a k < 2 n - 1

akZ>0
k=0n1ak<2n1

Según el principio del casillero, deben existir dos subconjuntos disjuntos, manera que:S1,S2{1,,n}

jS1aj=kS2ak

El problema de suma de subconjuntos de casilleros pide una solución de este tipo. Originalmente indicado en " Algoritmos de aproximación eficientes para el problema de IGUALDAD SUBSET-SUMS" por Bazgan, Santha y Tuza.

usuario834
fuente
16

Hay muchos problemas relacionados con la búsqueda de subgrupos ocultos. Usted mencionó la factorización, pero también existe el problema de registro discreto, así como otros relacionados con curvas elípticas, etc.

Joe Fitzsimons
fuente
15

Aquí hay un problema en la elección social computacional que no se sabe que está en P, y puede o no ser NP-completo.

Control de agenda para torneos equilibrados de eliminación simple:

Tn=2ka

Pregunta: ¿existe una permutación de los nodos (un paréntesis ) para que a sea el ganador del torneo de eliminación simple inducido?

Pk2kVTVPk12k1i>0Pk[2i1]Pk[2i]eTPk1[i]=Pk[2i1]e=(Pk[2i1],Pk[2i])Pk1[i]=Pk[2i]PkTPk12kkPk1,,P02k

Control de agenda para torneos equilibrados de eliminación simple (formulación de gráficos):

Tn=2ka

T2ka

2kxa2k1x2k1yxyk=0

Algunas referencias:

  1. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh: determinación del ganador en la votación por mayoría secuencial. IJCAI 2007: 1372-1377.
  2. N. Hazon, PE Dunne, S. Kraus y M. Wooldridge. Cómo organizar elecciones y concursos. COMSOC 2008.
  3. Thuc Vu, Alon Altman, Yoav Shoham. Sobre la complejidad de los problemas de control de horarios para torneos eliminados. AAMAS (1) 2009: 225-232.
  4. V. Vassilevska Williams. Arreglando un torneo. AAAI 2010.
virgi
fuente
13

Echa un vistazo a la clase TFNP . Tiene muchos problemas de búsqueda con un estado intermedio.

Marcos Villagra
fuente
NPcoNP
12

El problema del isomorfismo del subgrafo inducido tiene "restricciones del lado izquierdo" incompletas de NP, suponiendo que P no es igual a NP. Ver Y. Chen, M. Thurley, M. Weyer: Comprender la complejidad de los isomorfismos inducidos por el subgrafo , ICALP 2008.

Holger
fuente
2
Aunque este es un resultado interesante, si revisa el documento, incluso dice que la prueba de complejidad intermedia es esencialmente la misma que el Teorema de Ladner, excepto que usted hace la diagonalización en la elección de la restricción LHS. Así que no sé si esto cuenta como un problema "natural", en lugar de simplemente una codificación diferente del Teorema de Ladner.
Joshua Grochow
Tenga en cuenta también que estas son restricciones de origen y destino. El objetivo (lado derecho) debe ser de forma especial, para imponer la inyectividad.
András Salamon
10

El problema del material de corte con un número constante de longitudes de objeto. Vea esta discusión para más información.

Suresh Venkat
fuente
10

nv1vβvβ>1

β=nNPcoNPNPPββ=no(1/loglogn)NP

MCH
fuente
9

G=(V,E)fvVf(v)e=uvE|f(u)f(v)|f:V{0,1,2,,|E|}{1,2,...,|E|}

  1. JA Gallian. Una encuesta dinámica de etiquetado gráfico. The Electronic Journal of Combinatorics, 2009.
  2. DS Johnson. La columna de completitud NP: una guía continua. J. Algoritmos, 4 (1): 87–100, 1983.
  3. DS Johnson. La columna de completitud NP. ACM Transactions on Algorithms, 1 (1): 160–176, 2005.
Oleksandr Bondarenko
fuente
9

PNPO(nlogn)NPNP

Mohammad Al-Turkistany
fuente
LOGNPNP[log2n]
8

abax+1b

γ

Garey y Johnson en su seminal "Computadoras e Intractabilidad" dicen que (pp. 158-159):

γRMM

RM={x,y:there is a string z such that on input x and guess z M has output y}

L1Σ1γL2Σ2L1γL2MxΣ1yΣ2x,yRMx,yRMxL1yL2MxxxL2xL1

Oleksandr Bondarenko
fuente
γ
6

PNPO(nlogn)

Mohammad Al-Turkistany
fuente
5

Se cree que el siguiente problema es NP-Intermedio, es decir, está en NP pero no en P ni en NP-completo.

Problema exponencial de raíz polinómica (EPRP)

p(x)deg(p)0GF(q)qr

p(x)=rx
p(x)rxrxr

deg(p)=0

Para detalles adicionales vea mi pregunta y discusión relacionada .

Massimo Cafaro
fuente
4

No sé si el problema de isomorfismo de hipergrafía ponderada propuesto en la respuesta por Thinh D. Nguyen no puede mostrarse simplemente como GI completo. Sin embargo, hay un problema difícil de GI estrechamente relacionado con GI, que aún no se ha reducido a GI, a saber, el problema de isomorfismo de cuerdas (también llamado problema de isomorfismo de color ). Este es el problema que László Babai demostró estar en tiempo casi polinomial. Es de interés independiente, ya que es equivalente a una serie de problemas de decisión en la teoría de grupos (permutación):

Thomas Klimpel
fuente
3

Un problema que no se sabe que está en FP o NP-hard es el problema de encontrar un árbol Steiner mínimo cuando se promete que los vértices Steiner caerán en dos segmentos de línea recta que se cruzan en un ángulo de 120 °. Si el ángulo entre los segmentos de línea es inferior a 120 °, entonces el problema es NP-duro. Se conjetura que cuando el ángulo es mayor de 120 °, entonces el problema está en FP.

Por lo tanto, el siguiente problema de decisión actualmente parece ser de complejidad intermedia:


q
q

Por supuesto, esto en realidad puede estar en P o ser NP completo, pero entonces parece que tendríamos una dicotomía interesante a 120 ° en lugar de un problema intermedio. (La conjetura también puede ser falsa).

  • JH Rubinstein, DA Thomas, NC Wormald, Steiner Trees for Terminals Constrained to Curves , SIAM J. Discrete Math. 10 (1) 1–17, 1997. doi: 10.1137 / S0895480192241190
András Salamon
fuente