Problemas conocidos tanto en NP como en coNP, pero no en P

Question

Uno de esos problemas que conozco es la factorización de enteros.

¿Cuáles son otros casos interesantes?

Answer 1

Uno de mis favoritos de los problemas en NP $\cap$ co-NP es decidir quién gana una simple estocástico juego. El juego es jugado en un gráfico dirigido por dos jugadores, llamar a y B. Este gráfico contiene varios tipos de nodos. Hay un nodo fuente y fregadero de dos nodos, uno por cada uno de los jugadores. También hay aleatoria de nodos (que incluyen la fuente), "a" nodos, y "B" nodos. En el inicio del juego, para cada "a" o "B" nodo, el correspondiente jugador elige una de las aristas que salen de él, sin ver las otras elecciones del jugador.

Un token es luego colocado en el nodo de inicio. El token se somete a un paseo aleatorio. Cuando se golpea con un nodo aleatorio, se elige al azar entre los bordes dirigida lejos de este nodo. Cuando se golpea con Una "a" o "B" nodo, el token se lleva el elegido borde.

Cada jugador objetivo es maximizar la probabilidad de que el token de tierras en su nodo receptor. La pregunta en NP $\cap$ co-NP es: ¿Un jugador tiene una estrategia ganadora que garantiza el token de tierras en su nodo receptor con una probabilidad de al menos $\frac{1}{2}$?

Answer 2

Bajo populares derandomization supuestos, los siguientes problemas son en $NP\cap coNP$:

• Gráfico de Isomorfismo y Automorphism (así como el Grupo de Isomorfismo, Anillo de Isomorfismo, ...)
• Grupo de Pertenencia (por ejemplo, dado invertible matrices $A$ e $B_1,...,B_k$ es $A$ en el grupo generado por $B_1,...,B_k$?)

(Más precisamente, estos problemas son conocidos por ser en $NP\cap coAM$. $coAM$ es un "primos" de $coNP$, y es igual a la de este último en virtud de derandomization hipótesis: consulte este documento por Klivans y van Melkebeek.)

Además de factoring, hay varios otros número teórico de los problemas en $NP\cap coNP$, tales como la toma versiones de Logaritmo Discreto (en $Z_p^*$ y en curva elíptica grupos).

Si usted está dispuesto a permitir que la promesa de problemas (es decir, el algoritmo sólo se tiene a la salida de una respuesta correcta si la entrada satisface una propiedad), entonces hay un montón de ejemplos naturales de $NP\cap coNP$ de los problemas. Un ejemplo trivial es, "dado dos Booleanos fórmulas F y G, y prometió que exactamente uno de ellos es válido, decidir qué." Un ejemplo no trivial es el Aproximado Menor Vector problema, mencionado anteriormente por Niel. Lo más raro son interesantes $NP\cap coNP$ problemas que no tienen una promesa (o donde la promesa es fácil de comprobar).

Answer 3

Hay una lista corta en http://kintali.wordpress.com/2010/06/06/np-intersect-conp/

Answer 4

Supongamos que$K$ es un nudo en las tres esferas. Luego, decidir si$K$ es el nudo está en NP y también en co-NP. Su contención en NP se debe a Hass, Lagarias y Pippenger y la contención en co-NP ha sido mostrada (¿pero aún no escrita?) Por Agol.

Answer 5

Un entramado L es la imagen de ℤⁿ ⊂ ℝⁿ bajo la acción de una matriz de UN ∈ GL(ℝⁿ). El rango de L es la dimensión n del espacio que vive en.

• El vector más cercano problema (CVP) pregunta, para un vector x ∈ ℝⁿ, si el más cercano elemento de L es "cerrar" para x (distancia en la mayoría de los 1 en la norma Euclídea) o no.
• El menor vector problema (SVP) se pregunta si el menor elemento no nulo de L es "corto" (tiene una longitud máxima de 1) o no.

Ambos problemas son NP-completos. Hay un activo programa de investigación en la búsqueda eficiente de solucionable aproximación versiones, los cuales pueden ser interpretados como problemas en los que se le ha prometido que no es una aproximación del factor de brecha de f(n) entre SÍ y las instancias de NINGUNA de las instancias. Esto introduce la promesa de problemas de las familias

• GapCVP_f(n)
  --- la pregunta de si el más cercano al vector de L a x es "cerrar" (distancia máxima de 1 km) o "mucho" (distancia de al menos f(n) de distancia), dado que al menos uno de ellos es verdadero;

• GapSVP_f(n)
  --- la pregunta de si el menor no-vector cero en L es "corto" (longitud 1) o "largo" (longitud de, al menos, f(n)), dado que al menos una de ellas es verdadera.

El papel de "Celosía problemas en NP ∩ coNP" muestra que la aproximación a los problemas de GapCVP_√n y GapSVP_√n son tanto (como se puede adivinar) NP ∩ coNP; además, los testigos para SÍ y NO de las instancias, en principio, puede ser generado a partir de una determinada distribución de probabilidad, y por lo tanto son, en cierto sentido, abundante para esta aproximación factor.