Mi profesor hizo la declaración
Cualquier problema finito no puede ser NP-Complete
Estaba hablando de Sudoku en ese momento diciendo algo similar a que para un Sudoku 8x8 hay un conjunto finito de soluciones, pero no puedo recordar exactamente lo que dijo. Escribí la nota que he citado pero que todavía no entiendo.
Los Sudoku son NP completos si no me equivoco. El problema de la camarilla también es NP-Complete y si tuviera un problema de 4-Clique, ¿no es este un problema finito que es NP-Complete?
np-complete
np
TheRapture87
fuente
fuente
Respuestas:
Si un problema finito es NP-completo, entonces P = NP, ya que cada problema finito tiene un algoritmo de tiempo polinómico (incluso un algoritmo de tiempo constante).
Cuando decimos que Sudoku es NP-complete, queremos decir que una versión generalizada de Sudoku jugada en un tablero es NP-complete.norte2× n2
Finalmente, el problema de las 4 camarillas, aunque no es un problema finito (el gráfico de entrada tiene un tamaño ilimitado), es un problema fácil que tiene un algoritmo de tiempo polinómico.
fuente
La declaración de su maestro es incorrecta o probablemente no lo escuchó correctamente. La afirmación correcta es
El sudoku o el ajedrez no son NP completos (como Yuval ha señalado), porque su entrada es de tamaño finito de tablero 9x9 u 8x8 (estoy hablando de las versiones de decisión, si el sudoku tiene una solución o si el ajedrez tiene una estrategia ganadora). En ajedrez, supongo que si repites una posición, se considera un empate.
fuente
Recordemos: Un problema X es NP-completo si cumple dos criterios:
a) Está en NP: es decir, cualquier solución adivinada de X puede verificarse en tiempo polinómico.
b) Está completo para NP - Es decir, cada problema Y en NP tiene una reducción de tiempo polinomial que traduce una instancia de Y a una instancia de X (de modo que cualquier programa de tiempo polinomial que resuelva X también resolvería Y en tiempo polinómico )
Podemos aceptar que un Sudoku 9x9 satisface (a). Es (b) donde las cosas se caen. De manera más general: los problemas (en NP o no) suelen tener instancias de tamaño N para valores arbitrariamente grandes de N ; ciertamente esto es cierto para los problemas conocidos en NP. Una reducción de tal problema a uno que tenga un tamaño de problema máximo posible no podría ser una reducción de instancia a instancia válida, porque la primera siempre tiene (infinitamente) más instancias que la segunda. Es por eso que Sudoku debe generalizarse a las matrices NxN antes de que uno pueda considerar la completitud NP.
fuente