Siento que debería haber un ejemplo fácil, pero no puedo pensar en uno. Entonces, específicamente, estoy buscando un problema de búsqueda Sí/No que no esté en la clase NP. Cuando aprendes sobre P y NP, obtienes muchos ejemplos de problemas en P, NP, NP-difícil, NP-completo, co-NP, etc. Supongo que el problema de detención funcionaría, pero me gustaría algo para lo cual la computabilidad no es la razón por la que no es NP.
Puede usar el teorema de la jerarquía del tiempo para fabricar problemas que tienen respuestas de sí/no pero que no están en NP, por ejemplo, requiriendo que tomen al menos una cantidad superpolinomial de tiempo no determinista para calcular.
Otra opción es mirar los problemas NEXP-completos . El teorema de la jerarquía temporal garantiza que ninguno de estos problemas se pueda resolver en un tiempo polinomial no determinista, pero todos son problemas de sí/no.
En realidad, ¡tal problema no existe! Sabemos esto porque la forma en que definimos la clase NP es esencialmente como la clase de todos los problemas de búsqueda. Recuerde que cualquier problema de búsqueda puede definirse mediante una instancia de entrada I y un algoritmo de verificación C, donde C(I) devuelve verdadero si y solo si satisface las restricciones que queremos. C debe hacer esto en tiempo polinomial. En el caso del problema de decisión del viajante de comercio, C verifique que nuestra instancia I (un camino en un gráfico) sea un ciclo, toque todos los vértices exactamente una vez y tenga un peso menor que algún presupuesto b. Entonces, aunque todos los problemas en NP no parecen problemas de búsqueda al principio, lo son. Sabemos esto porque para todos los problemas en NP, podemos resolverlos a través de una búsqueda exhaustiva (iterando a través de todas las entradas válidas posibles a C y viendo si alguna devuelve True).
tomgrubb
MonadBoy
MonadBoy
Alex