Esta pregunta fue inspirada por un comentario en StackOverflow .
Además de conocer los problemas NP-completos del libro de Garey Johnson, y muchos otros; ¿Existe una regla general para saber si un problema se parece a un NP completo?
No busco algo riguroso, sino algo que funcione en la mayoría de los casos.
Por supuesto, cada vez que tenemos que demostrar que un problema es NP completo, o una ligera variante de un NP completo; pero antes de apresurarse a la prueba sería genial tener cierta confianza en el resultado positivo de la prueba.
complexity-theory
np-complete
intuition
Виталий Олегович
fuente
fuente
Respuestas:
Este es mi enfoque personal para determinar si un problema (es decir, un lenguaje ) es NP-completo o no. Si se verifican ambas condiciones:L
Francamente, este enfoque es muy básico: trato de encontrar un algoritmo (polinómico) para el problema dado. Si no puedo encontrar uno, el problema se vuelve "difícil" en mi punto de vista. Luego viene todo el razonamiento de NP-completeness: ¿podré codificar un problema NP-complete existente en este? (Y dado que esto suele ser mucho más difícil, intento una vez más encontrar un algoritmo polinomial ...)
Sospecho que esta es la forma habitual de pensar. Sin embargo, sigue siendo bastante difícil de aplicar en problemas desconocidos. Personalmente recuerdo que me sorprendió uno de los primeros ejemplos de integridad de NP que me dijeron: el problema de la camarilla . ¡Parecía tan simple de verificar! Así que supongo que esa experiencia tiene mucho que ver con eso. También la intuición puede ser inútil a veces. Recuerdo que me dijeron varias veces dos problemas casi idénticos, pero uno estaba en P y el otro con una pequeña variación era NP completo.
Todavía tengo que encontrar un buen ejemplo (necesito ayuda aquí), pero esto es como el problema de la correspondencia posterior : este es un problema indecidible pero algunas variantes son decidibles.
fuente
Otra perspectiva sobre la dureza del problema proviene de la comunidad de juegos y acertijos, donde la regla general es que "los problemas son tan difíciles como pueden ser" (y las excepciones provienen de estructuras ocultas en el problema - el ejemplo de Massimo del determinante en comentarios es una buena instancia de esto); El truco es comprender cuán difícil puede ser un problema:
fuente