¿Hay problemas de "NP-Intermedio-Completo"?

13

Suponga P NP.≠

El teorema de Ladner dice que hay problemas NP intermedios (problemas en NP que no están en P ni en NP-Complete). Encontré algunas referencias veladas en línea que sugieren (creo) que hay muchos "niveles" de lenguajes mutuamente reducibles dentro de NPI que definitivamente no todos colapsan en uno.

Tengo algunas preguntas sobre la estructura de estos niveles.

  1. ¿Existen problemas de "NP-Intermedio-Completo", es decir, problemas de NP-Intermedio a los cuales cualquier otro problema de NP-Intermedio es politemporalmente reducible?
  2. Clasifique NP - P en clases de equivalencia, donde la reducibilidad mutua es la relación de equivalencia. Ahora imponga un orden en estas clases de equivalencia: si los problemas en reducen a problemas en (por lo que claramente la clase de equivalencia NP-completa es el elemento máximo). ¿Es este un pedido total (es decir, los problemas se organizan en una cadena descendente infinita)? Si no, ¿la "estructura de árbol" de la ordenación parcial tiene un factor de ramificación finito?B AA>BBA
  3. ¿Hay otros componentes estructurales conocidos interesantes de NP - P? ¿Hay alguna pregunta abierta interesante sobre la estructura subyacente?

Si alguno de estos es actualmente desconocido, me interesaría escuchar eso también.

¡Gracias!

cc.complexity-theory np np-intermediate GMB
fuente
3
Una versión débil de esto es que hay problemas de "Graph-Isomorphism-Complete".
Suresh Venkat
77
La respuesta a 1. es "sí y no". Creo que sí, porque como dice Suresh, puede tener problemas GI-complete (y -complete problemas para otros problemas ). Y no porque, según la prueba de Ladner, existe una jerarquía infinita de clases intermedias y, si no me equivoco, tener un problema -completo completo colapsaría esta jerarquía (y por lo tanto, por contradicción, se demuestra ), de la misma manera que la jerarquía polinómica no puede tener un problema completo si no colapsa. π N P N P P = N PππNPNPP=NP
Bruno
Gracias, Bruno. ¿Se puede encontrar toda esta información en el documento original de Ladner o hay otras fuentes relevantes?
GMB
También puede consultar el artículo de Downey y Fortnow: Uniformly Hard Languages ; en el que la demostración del teorema de Ladner que figura en el Apéndice A.1 muestra que los grados de tiempo polinomiales de los lenguajes computables son un ordenamiento parcial denso. También conjeturan que si existen conjuntos uniformemente duros en NP, entonces existen conjuntos incompletos uniformemente duros.
Marzio De Biasi
1
para otra referencia para 1. y un recurso posiblemente útil, vea la respuesta de Ryan y el artículo de Schoening citado en él.
Sasho Nikolov

Respuestas:

31

Realmente no tengo referencias para estos resultados, no son difíciles de probar una vez que entiendes el teorema de Ladner.

  1. No, para cualquier conjunto A NP incompleto, hay otro conjunto B estrictamente entre A y SAT.

  2. Estas clases de equivalencia se conocen como polinomios-muchos-uno grados. Puede incrustar cualquier poset finito en los grados por debajo de NP. En particular, los grados no están totalmente ordenados o se ramifican finitamente.

  3. Todo esto depende de lo que quieras decir con "interesante". Existe una gran teoría de la estructura de grados de los conjuntos computables (ver el libro de Soare, por ejemplo) y muchas de esas preguntas no se han trasladado a conjuntos de tiempo polinómico. Por ejemplo, ¿puede tener conjuntos NP A y B cuya unión sea equivalente a SAT y cuya reunión sea equivalente al conjunto vacío?

Lance Fortnow
fuente
1
¿Qué quieres decir con encuentro, algún tipo de intersección? Supongo que la unión de y es tal que iff e , ¿es correcto? B C ( x , y ) ∈ C x ∈ A y ∈ BABC(x,y)∈Cx∈Ay∈B
John D.
8
Estos son términos de la teoría reticular : la unen de un subconjunto es su extremo superior (si existe) y el se encuentran el mayor límite inferior.
Bruno