Problemas NP-completos no "obviamente" en NP

27

A muchos se les ocurrió que en todas las pruebas de que he leído (que puedo recordar), siempre es trivial mostrar que hay un problema en , y mostrar que es -duro es la ... parte difícil. ¿Qué problemas -completos son estos cuyos verificadores de tiempo polinómico son altamente no triviales?notario públiconotario públiconotario públiconotario público

cabeza de jardín
fuente
99
No es NP completo, pero mostrar membresía en NP de probar si un número es primo no es trivial (en lugar de mostrar que es un compuesto, que es trivial). Por supuesto, ahora se sabe que el problema está en P, pero aún así, este es un verificador intrigante.
Shaull
2
Probar que el "PRIME" está en NP fue definitivamente mucho más difícil que demostrar que la mayoría de los problemas completos de NP están en NP.
gnasher729
1
Consulte también la pregunta más general cstheory.stackexchange.com/q/21106/109 en CS.SE.
András Salamon

Respuestas:

19

Hay al menos cuatro de estos completos de enumerados en el apéndice de COMPUTADORAS E INTRACTABILIDAD de Garey y Johnson : una guía para la teoría de la integridad de NP .nortePAGS

[AN6] NO DIVISIBILIDAD DE UN PRODUCTO POLINOMIAL

INSTANCIA: Secuencias de pares de enteros , con cada b_i [j] \ geqslant 0, y un número entero N .b i [ j ] 0 , NAi=(ai[1],bi[1]),...,(ai[k],bi[k]), 1im,bi[j]0,N

PREGUNTA: ¿ i=1m(j=1kai[j]zbi[j]) no es divisible por zN1 ?

Referencia: [Plaisted, 1977a] , [Plaisted, 1977b] . Transformación de 3SAT. La prueba de membresía en NP no es trivial y aparece en la segunda referencia.

Los otros tres que encontré en el apéndice son:

  • [LO13] MODAL LOGIC S5-SATISFIABILITY
  • [LO19] INSTANTIACIÓN DE SEGUNDO ORDEN
  • [MS3] NO VIDA DE REDES PETRI DE ELECCIÓN GRATUITA
Kyle Jones
fuente
¡Gracias! Tengo este libro, así que me aseguraré de leerlo.
cabeza de jardín
No estoy muy claro con respecto a este problema: (1) ¿Estoy en lo correcto al interpretar que z es una variable que puede tomar cualquier valor entero (al igual que una ecuación lineal / cuadrática ordinaria)? (2) Por lo tanto, la no divisibilidad sería equivalente a decir que: "para ningún valor entero de la ecuación z A es divisible por B"?
TheoryQuest1
1
Lo que deduje al leer las primeras dos páginas del artículo de 1977a es que es una cantidad relacionada con el número de ceros del polinomio que es parte de la entrada. Por más que eso, me temo que tendrás que revisar el periódico. z
Kyle Jones
4

Aquí hay un problema de la teoría de la base de datos, más específicamente, de la teoría de serialización.

En Serializability by Locking (Página 237) , dice que

En cuanto a la complejidad de la seguridad, Papadimitriou et al. [14] demostró que es difícil probar si un sistema de transacción no es seguro para S S R , y conjeturó que el problema es NP . Del teorema 3 (en este documento), se deduce que esto es cierto.NPSSRNP

El problema -safe se puede encontrar en el documento "Algunos problemas computacionales relacionados con el control de concurrencia de bases de datos" de Papadimitriou et al. Lamentablemente, no tengo acceso a él.SSR

hengxina
fuente
2

Para mí, la programación lineal de enteros (y la aritmética de presburger libre de cuantificador relacionada) están en esta clase.

Un enfoque ingenuo para un problema ILP dimensional es iterar a través de todos los vectores n de longitud de enteros. Pero este es un proceso ilimitado.nn

Debe usar alguna teoría de números para demostrar que hay un límite superior polinómico en el tamaño de las soluciones, lo que significa que si existe una solución, siempre hay una solución de tamaño polinómico, que actúa como un certificado.

Puede encontrar más información en la respuesta a una pregunta que hice hace un tiempo.

jmite
fuente