Membresía no trivial en NP

¿Hay un ejemplo de un idioma que está en , pero donde no podemos probar este hecho directamente al mostrar que existe un testigo polinómico para la membresía en este idioma?$NP$

En cambio, el hecho de que el idioma está en se probaría reduciéndolo a otro idioma en , donde el vínculo entre los dos no es trivial y necesita un análisis cuidadoso.$NP$$NP$

En términos más generales, ¿hay algunos ejemplos interesantes de problemas en para que sea difícil ver que están en ?$NP$$NP$

Una semi-respuesta sería el problema de decidir el ganador en los juegos de paridad: para demostrar que está en (incluso ), necesitamos el teorema de determinación de posición que es profundo y no trivial. Sin embargo, esta respuesta no es ideal, porque todavía se reduce a la existencia de un testigo polinómico para este problema exacto (la estrategia posicional), y no se reduce a otro diferente .$NP$$NP\cap coNP$$NP$

Otro sería el algoritmo de primalidad AKS: decidir si un número es primo es polinómico, mientras que a priori no hay un pequeño testigo de este hecho. Digamos que descartamos los "algoritmos polinomiales sorprendentes", ya que muchos de ellos encajarían en la descripción anterior. Estoy más interesado en algoritmos sorprendentes que no son deterministas.$NP$

Programación de enteros .

Demostrar que si hay una solución entera entonces hay una solución entera de tamaño polinómico está bastante involucrada. Ver

• Christos Papadimitriou, " Sobre la complejidad de la programación de enteros ", JACM, 1981.

Mientras que el problema "es el número de cruce de un gráfico como máximo ?" es trivial en NP, la membresía de NP de los problemas relacionados para el número de cruce rectilíneo y el número de cruce de pares no es muy obvio; cf. Bienstock, Algunos problemas de números probablemente cruzados, Computo discreto. Geometry 6 (1991) 443-459, y Schaefer et al., Reconociendo gráficos de cuerdas en NP, J. Comput. System Sci. 67 (2003) 365-380.$k$

Mi ejemplo favorito es un clásico resultado de 1977 de Ashok Chandra y Philip Merlin. Mostraron que el problema de contención de consultas era decidible para consultas conjuntivas. El problema de contención de consultas conjuntas resulta ser equivalente a decidir si existe un homomorfismo entre las dos consultas de entrada. Esto reformula un problema de semántica, que implica la cuantificación sobre un conjunto infinito, en uno sintáctico, que solo requiere verificar un número finito de posibles homomorfismos. El certificado de homomorfismo es solo de tamaño lineal y, por lo tanto, el problema está en NP.

Este teorema proporciona uno de los fundamentos de la teoría de optimización de consultas de bases de datos. La idea es transformar una consulta en otra más rápida. Sin embargo, uno quiere asegurarse de que el proceso de optimización no cree una nueva consulta que no proporcione respuestas en algunas bases de datos donde la consulta original sí produjo resultados.

Formalmente, una consulta de base de datos es una expresión de la forma , donde x es una lista de variables libres, y es una lista de variables enlazadas, y Q ( x , y ) es una fórmula de primer orden con variables x e y de un lenguaje con símbolos de relación. La consulta Q puede contener cuantificadores existenciales y universales, la fórmula puede contener conjunción y disyunción de átomos relacionales, y también puede aparecer negación. Se aplica una consulta a una instancia de base de datos $\mathbf{x}.Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q$$I$, que es un conjunto de relaciones. El resultado es un conjunto de tuplas; cuando la tupla en el resultado se sustituye por x, entonces se puede satisfacer la fórmula Q ( t , y ) . Uno puede entonces comparar dos consultas: Q 1 está contenida en Q 2 si siempre que Q 1 aplicado a un ejemplo de base de datos arbitraria I produce algunos resultados, entonces Q 2 aplicada a la misma instancia que también produce algunos resultados. (Está bien si Q 1 no produce resultados pero Q $\mathbf{t}$$\mathbf{x}$$Q(\mathbf{t},\mathbf{y})$$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$$Q_1$$Q_2$no, pero para la contención de la implicación debe mantener durante todos los casos posibles) El. problema de contención consulta se pregunta: Dadas dos bases de datos consulta y Q 2 , se Q 1 contenida en Q 2 ?$Q_1$$Q_2$$Q_1$$Q_2$

Antes de Chandra-Merlin no estaba del todo claro que el problema fuera decidible. Usando solo la definición, uno tiene que cuantificar sobre el conjunto infinito de todas las bases de datos posibles. Si las consultas no están restringidas, el problema es, de hecho, indecidible: dejar que sea ​​una fórmula que siempre es verdadera, entonces Q 1 está contenido en Q 2 si Q 2 es válido. (Este es el problema Entscheidungs de Hilbert , que Church and Turing demostró indecidible en 1936).$Q_1$$Q_1$$Q_2$$Q_2$

Para evitar la indecidibilidad, una consulta conjuntiva tiene una forma bastante limitada: solo contiene cuantificadores existenciales, y la negación y la disyunción no están permitidas. Entonces Q es una fórmula existencial positiva con solo conjunción de átomos relacionales. Este es un pequeño fragmento de lógica, pero es suficiente para expresar una gran proporción de consultas útiles en la base de datos. La declaración clásica en SQL expresa consultas conjuntivas; La mayoría de las consultas de motores de búsqueda son consultas conjuntas.$Q$$Q$SELECT ... FROM

Se pueden definir homomorfismos entre consultas de una manera directa (similar al homomorfismo gráfico, con un poco de contabilidad adicional). El teorema de Chandra-Merlin dice: dadas dos consultas conjuntas y Q 2 , Q 1 está contenido en Q 2 si hay una consulta homomorfismo de Q 2 a Q 1 . Esto establece la membresía en NP, y es sencillo demostrar que esto también es NP-hard.$Q_1$$Q_2$$Q_1$$Q_2$$Q_2$$Q_1$

• Ashok K. Chandra y Philip M. Merlin, Implementación óptima de consultas conjuntas en bases de datos relacionales , STOC '77 77–90. doi: 10.1145 / 800105.803397

La capacidad de decisión de la contención de consultas se extendió más tarde a las uniones de consultas conjuntivas (consultas positivas existenciales donde se permite la disyunción), aunque permitir la disyunción aumenta la complejidad a -completo. Los resultados de decidibilidad e indecidibilidad también se han establecido para una forma más general de contención de consultas , que implican valoraciones de semiring que se producen al contar el número de respuestas, al combinar anotaciones en la procedencia o al combinar resultados de consultas en bases de datos probabilísticas.$\Pi^P_2$

Encontré un buen candidato mientras leía algunos documentos sobre ecuaciones de diofantina cuadráticas:

JC Lagarias, certificados sucintos para soluciones a ecuaciones binarias cuadráticas de diofantina (2006)

Del resumen: ... Sea la longitud de la codificación binaria de la ecuación binaria cuadrática de diofantina F dada por a x 2 1 + b x 1 x 2 + c x 2 2 + d x 1 + e x 2 + f = 0 . Suponga que F es una ecuación que tiene una solución entera no negativa. Este documento muestra que hay una prueba (es decir, "certificado") de que F tiene una solución que se puede verificar en$L(F)$$F$$a x_1^2 +b x_1 x_2+ c x_2^2 +d x_1+e x_2 + f = 0$$F$$F$ operaciones de bit. Un corolario de este resultado es que el conjunto Σ = { F : F  tiene una solución entera no negativa } está en la clase de complejidad NP ...$O(L(F)^5 \log L(F) \log \log L(F))$$\Sigma = \{F : F \text{ has a nonnegative integer solution}\}$

... pero, para ser sincero, la única evidencia que tengo de que no es trivial es el número de páginas del documento ... 62! :-)

Cuando se abrió el reconocimiento del gráfico de tolerancia, el siguiente documento mostró que está en NP:

http://www.sciencedirect.com/science/article/pii/S0166218X04000940

(Más adelante, se demostró que el reconocimiento del gráfico de tolerancia era NP completo: http://arxiv.org/abs/1001.3251 )

Decidir la accesibilidad para varios tipos de sistemas de estado infinito a veces es decidible, a menudo no. Para algunos casos especiales interesantes, siempre existe un certificado suficientemente pequeño y eficientemente comprobable, que pone tales problemas en NP. Aquí hay un tratamiento ordenado para autómatas paramétricos de un contador:

• Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, Accesibilidad en autómatas sucintos y paramétricos de un contador , CONCUR 2009, LNCS 5710 369–383. doi: 10.1007 / 978-3-642-04081-8_25 ( versión extendida )

Aquí hay un ejemplo (aunque ciertamente artificial) cuando es muy difícil decidir si un problema está en o no. Let L 1 , L 2 haber dos idiomas, con L 1 ∈ N P , y L 2 ∉ N P . Ahora defina el lenguaje L , como sigue:$NP$$L_1, L_2$$L_1\in NP$$L_2\notin NP$$L$

$L\in NP$$L\in NP$$NP$