Problemas NP-completos no "obviamente" en NP

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?$\textbf{NP}$$\textbf{NP}$$\textbf{NP}$$\textbf{NP}$

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 .$NP$

[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 , $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$$b_i[j] \geqslant 0,$$N$

PREGUNTA: ¿ $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ no es divisible por $z^N - 1$ ?

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

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.$\textrm{NP}$$SSR$$\textrm{NP}$

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$

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.$n$$n$

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.