#4110 Problema NP no es lo mismo que problema indecidible. Ojo con los términos. Los problemas que he comentado no son NP ni NP-completos, son problemas para los cuales no existe algoritmo que los resuelva (sobre una máquina de Turing o equivalentes) ante cualquier posible entrada.
Por cierto, no es mi tema pero creo que se ha demostrado que el sudoku es NP-completo. Que conste que no estoy seguro de esto, simplemente me suena. Si fuese así y encontraras un algoritmo que lo resuelva en tiempo polinomial te dan un premio Nobel como mínimo xD