Sí, cualquier lenguaje en P o NP es decidible.
Primero, 2 definiciones:
- NP es la clase de lenguajes que puede reconocer una máquina de Turing no determinista en tiempo polinomial (http://en.wikipedia.org/wiki/NP_…).
- Un lenguaje decidible es un lenguaje formal para el que existe una máquina de Turing que, cuando se le presenta una cadena de entrada finita, se detendrá y aceptará si la cadena está en el idioma, y se detendrá y rechazará de otra manera. La máquina de Turing siempre se detiene; se conoce como un decisor y se dice que decide el idioma. (http://en.wikipedia.org/wiki/Dec…)
Dado que cualquier lenguaje en NP puede ser reconocido por una máquina Turing (TM) no determinista en tiempo polinómico, significa que hay una máquina Turing que siempre se detiene cuando se le presenta cualquier cadena de entrada finita del lenguaje.
- ¿Podría la programación de aprendizaje y las matemáticas cambiar mis patrones de pensamiento?
- ¿Cuál es el significado de las implicaciones teóricas?
- ¿Cómo valora las opciones sobre acciones utilizando la transformación de Fourier?
- Si resolvemos el problema del ciclo de Hamilton en el tiempo P, ¿eso realmente muestra P = NP?
- ¿Existe un número distinto de cero para el cual su representación doble y larga es equivalente en bits?
Por lo tanto, cualquier idioma en NP es decidible. Desde [math] P \ subset \ NP [/ math], cualquier lenguaje en P también es decidible.
