Preguntas de patrón para preguntas de NPC

Otro ejemplo interesante es el problema del isomorfismo de grafos, que es un método de la teoría de grafos para determinar si dos grafos son isomórficos. La condición intuitiva para que dos gráficas sean isomorfas es que si una gráfica puede coincidir con la otra moviendo los vértices, entonces las dos gráficas son isomorfas. Considere las siguientes dos preguntas:

Isomorfismo del gráfico: ¿El gráfico G1 es isomorfo al gráfico G2?

Isomorfismo del subgrafo: ¿Es el gráfico G1 isomorfo a cualquier subgrafo del gráfico G2?

Los problemas de isomorfismo de subgrafos son problemas de NPC, mientras que los problemas de isomorfismo de grafos generalmente no se consideran problemas P ni NPC, aunque son claramente problemas NP. Este es un ejemplo de algo que generalmente se considera difícil pero que aún no es un problema de NPC.

La forma más sencilla de demostrar que un problema es un problema de NPC es demostrar primero que es un problema de NPC y luego transformarlo en algún problema conocido como un problema de NPC. Por lo tanto, es útil familiarizarse con los diferentes tipos de problemas de NPC antes de aprender técnicas de conversión. La siguiente tabla enumera algunos problemas de NPC bien conocidos expresados ​​como proposiciones deterministas:

Problema de satisfacibilidad booleano: (Problema de satisfacibilidad booleano) (SAT)

Problema de rompecabezas de N palabras (problema de Waldorf): (N-puzzle)

Problema de la mochila: (Problema de la mochila)

Problema del ciclo hamiltoniano: (Problema del ciclo hamiltoniano)

Problema del viajante: (Problema del viajante )

Problema de isomorfismo de subgrafo: (Problema de isomorfismo de subgrafo)

Problema de suma de subconjunto

Problema de camarilla

Problema de cobertura de vértice

Problema de conjunto independiente

Problema de conjunto independiente

Problema de cobertura de vértice

Problema de conjunto independiente

Problema de conjunto independiente)

Problema de coloración de gráficos (ver Teorema de los cuatro colores): (problema de coloración de gráficos)

Para obtener más ejemplos de problemas de NPC, consulte Lista de problemas NP-completos (lista de problemas NP-difíciles).

A la derecha hay diagramas de flujo de algunos problemas de NPC, junto con transformaciones que demuestran que son problemas de NPC. En un diagrama de flujo, las flechas representan la transición de un problema a otro. Cabe señalar que este diagrama no representa la relación matemática entre estos problemas. De hecho, dos problemas cualesquiera con propiedades NPC se pueden transformar en tiempo polinómico. Este diagrama solo indica el orden de transformación del problema para los investigadores.