TEORIA DE LA COMPUTACION PROBLEMAS INDECIDIBLES E INTRATABLES

PROBLEMAS INDECIDIBLES E INTRATABLES En teora de la computacin, un problema indecidible es un problema de decisin para el cual es imposible construir un algoritmo sencillo que siempre conduzca a una respuesta de s o no correcta. Los problemas de decisin son cualquier pregunta arbitraria de si o no en un nmero infinito de entradas, estas entradas pueden ser de nmeros naturales, o valores de otrotipo como las cadenas. Los lenguajes no recursivamente enumerables La interpretacin de este hecho, es la existencia de ms problemas (lenguajes) que algoritmos (mquinas de Turing). En consecuencia, existen lenguajes que no son reconocibles mediante mquinas de Turing, i.e. no admiten ni siquiera una respuesta parcial al problema del reconocimiento de los mismos. Equivalentemente, existen problemaspara los que no ha y algoritmos. Un ejemplo de esto es el lenguaje diagonal, La interpretacin de la no recursividad enumerable de QUOTE es clara no existe un algoritmo capaz de reconocer QUOTE (siquiera de manera parcial), existen problemas que no admiten solucin algortmica. La definicin de dicho lenguaje es La demostracin de la no recursividad enumerable de QUOTE es Si QUOTE , setiene, de nuevo por la definicin de QUOTE , que si QUOTE . Al ser QUOTE , llegamos de nuevo a un absurdo. Por lo tanto, enambos casos llegamos a una contraddccion y por ende, QUOTE no puede ser recursivamente enumerable, en resumen el leguanje diagonal no admite una respuesta algortmica. Problemas indecidibles para mquinas de Turing Se utilizan los lenguajes Lu y Ld que ya conocemos paradescribir los problemas indecidibles para maquinas de Turing, para esto se aplica la tcnica de Reduccin. Reduccin Una manera ms simple de hacer esta operacin es utilizando el mtodo de reduccin, el cual est implcito en nuestra manera de pensar a la hora de solucionar ciertos problemas dado un problema P1, este se reduce a solucionar P2. Es decir, si solucionamos P2, tenemos solucionado P1. De estamanera hemos convertido un problema en otro. Un ejemplo de esto es P1.- Hay hambre en el mundo. P2.- Hay que redistribuir parte de la riqueza El problema del hambre en el mundo se reduce a redistribuir riqueza. P2 es un problema mucho ms general, pues adems de solucionar el hambre tambin solucionara otros ms. Hay que hacer notar que este mtodo no hace referencia a la manera en la que se soluciona P1o P2, sino que determina como la solucin de P2 conduce a solucionar P1. Tambin se puede ver que P2 es un problema ms general que P1. De hecho este mtodo no funcionara en el sentido inverso siempre se reduce un problema a otro ms general. PROBLEMAS INTRATABLES Con el tiempo se a realizado una distincin entre algoritmos de tiempo polinmico y algoritmos de tiempo exponencial cuando se trata decaracterizar a los algoritmos como suficientemente eficiente y muy ineficiente respectivamente. Un algoritmo de tiempo polinomial se define como aquel con funcin de complejidad temporal en O(p(n)) para alguna funcin polinmica p, donde n denota el tamao de la entrada. Cualquier algoritmo cuya funcin de complejidad temporal no pueda ser acotada de esta manera, se denomina algoritmo de tiempo exponencial.La mayora de los algoritmos de tiempo exponencial son simples variaciones de una bsqueda exhaustiva, mientras que los algoritmos de tiempo polinomial, usualmente se obtienen mediante un anlisis ms profundo de la estructura del problema. En la teora de la complejidad computacional, existe el consenso de que un problema no est bien resuelto hasta que se conozca un algoritmo de tiempo polinomial quelo resuelva. Por tanto, nos referiremos a un problema como intratable, si es tan difcil que no existe algoritmo de tiempo polinomial capaz de resolverlo. Clases P y NP a relacin entre las clases de complejidad P y NP es una pregunta que an no se ha podido responder por la teora de la complejidad computacional. En esencia, la pregunta es P NP significa si es posible verificar rpidamente...