Resumen de problemas np-completos

UNIVERSIDAD NACIONAL DE SAN AGUST´ IN AREQUIPA

Facultad de Ingenier´ de Producci´n y Servicios ıa o ESCUELA PROFESIONAL DE CIENCIA DE LA ´ COMPUTACION

Curso:
Teor´ de la Computaci´n - IV Semestre ıa o

Docente:
Lic. Wilber Ramos Lov´n o

Trabajo Encargado: Problemas NP-Completos Presentado por:
Quintanilla Cruz, Rommel Anatoli

Fuentes (Slides): Complejidad Computacional. CarlosG´mez Rodriguez o Complejidad y Optimizaci´n. Javier Andr´s Mena Zapata o e Problemas NP. Juan Rom´n Alonso a Complejidad de los Problemas. J.B. Hayet

I
Acerca de la complejidad computacional
La complejidad computacional estudia la “dificultad” inherente de problemas de importancia te´rica y/o pr´ctica ya que el esfuerzo necesario para resolver un problema de o a forma eficiente puede variarenormemente. Considera globalmente todos los algoritmos posibles para resolver un determinado problema. Existen diversas formas de medir la complejidad de un algoritmo. La complejidad se mide en funci´n del tama˜o de la entrada. La complejidad temporal se refiere al tiempo o n que se demora en ejecutarse un algoritmo, la complejidad espacial se refiere a la cantidad de memoria que ocupa un algoritmo yen general cuando no se especifique expl´ ıcitamente, se referir´ a la complejidad temporal. a La notaci´n asint´tica sirve para saber cuanto crece una funci´n con respecto a otra. o o o Como a algunos algoritmos se pueden medir por su complejidad respecto al tama˜o de la n entrada, se pueden hacer ciertas comparaciones con respecto al “mejor” algoritmo. Ejemplo: La ordenaci´n por selecci´n es O(n),la ordenaci´n por mont´ o o o ıculos es O(nlog(n)). ¿Cu´l es la mejor complejidad temporal que podemos conseguir para ordenar un array a de tama˜o n?. Sabemos que podemos hacerlo en O(nlog(n)) pero ¿podemos hacerlo m´s n a r´pido?, si la respuesta es “s´ podemos demostrarlo encontrando un algoritmo m´s r´pido. a ı” a a Si fuera “no”, buscar algoritmos mejores ser´ perder el tiempo. Por lo tantonecesitamos ıa razonar sobre el problema en su conjunto, m´s all´ de algoritmos concretos. a a

1

II
Clases de complejidad computacional
La mayor parte de los problemas en teor´ de la complejidad tienen que ver con los ıa problemas de decisi´n, que corresponden a poder dar una respuesta positiva o negativa a o un problema dado. Los problemas se clasifican en conjuntos o clases de complejidad(L, NL, P, P-Completo, NP, NP-Completo, NP-Duro ...). Se considera que un problema es tratable si se puede resolver en tiempo polin´mico o O(nk ) para alg´n k. Si no existe esa constante k entonces se dice que el algoritmo no tiene u complejidad polinomial. Veremos a continuaci´n un resumen de las clases P y NP. o

II.1.

Clase P

Contiene aquellos problemas de decisi´n que pueden serresueltos en tiempo polin´mio o co por una M´quina de Turing determinista, esto es, aquellas en las que para cada par a estado y s´ ımbolo exista a lo sumo una posibilidad de ejecuci´n. Los problemas de como plejidad polin´mica son tratables. o Ejemplo: ¿Existe un divisor com´n a dos enteros a y b? S´ es un problema de decisi´n. u ı, o Existe el algoritmo ingenuo de recorrido de los enteros entre 1 ymin(a, b) que es exponencial en el peor caso. Sin embargo tambi´n existe un algoritmo polinomial, el algoritmo de Euclides de e complejidad cuadr´tica sobre tama˜io de los datos. Por lo tanto es un problema P. a n

II.2.

Clase NP

Contiene los problemas de decisi´n que son resueltos por una M´quina de Turing no o a determinista en tiempo polin´mico y de ah´ su nombre: Non-DeterministicPolynomialo ı time. Dicho de otro modo, no se ha encontrado un algoritmo determinista que lo resuelva en tiempo polinomial. Adem´s contiene a los problemas que son verificables en tiempo a polinomial. Lo que se quiere decir es que si se tuviera alguna clase de “certificado” de una soluci´n, entonces, es posible verificar en tiempo polinomial que el certificado es correcto, o respecto al tama˜o de la...