Embed Size (px)
Citation preview
Análisis de algoritmos para determinar problemas P y NP Fernández, Santiago. [email protected]
Acevedo, Enzo. [email protected] Universidad Tecnológica Nacional, Facultad Regional Buenos Aires
Abstract
El presente trabajo describe qué es la Complejidad
Computacional, explicando sus inicios gracias a la
máquina de Turing. Además, detalla las clases de
complejidad P y NP y cuál es su relación con el
análisis de algoritmos. Se presenta esta relación ya
que para resolver problemas que se encuentren,
tanto en ambas clases de complejidad (P y NP), es
necesario contar con algoritmos eficientes. Por otra
parte, se realizó un análisis sobre los distintos
órdenes que puede tener un algoritmo (ya sea orden
lineal, logarítmico, constante, entre otros), con el fin
de observar la variación de eficiencia y cómo éstos
ordenes pueden alterar el tiempo de respuesta de un
algoritmo, ya sea un aumento mínimo de tiempo en
segundos/minutos o un aumento exponencial de
tiempo en años. Se concluye analizando por qué hay
que tener en cuenta algoritmos más eficientes a la
hora de hablar de clases de complejidad.
Palabras Clave: Máquina de Turing. Complejidad
Computacional. Clases de Complejidad.
Introducción
A la hora de identificar un problema
decidible (esto es, que exista un algoritmo
que pueda resolverlo en tiempo y con
recursos finitos) dentro de las clases de
complejidad P o NP, es de gran importancia
poder clasificarlo correctamente. En
principio, un problema que pareciera ser NP
(problemas que son resueltos por algún
algoritmo en tiempo no-polinomial) podría,
en verdad, estar contenido dentro del
conjunto P (problemas que son resueltos
por algún algoritmo en tiempo polinomial)
[1]. Las clases de complejidad (P y NP)
están estrechamente relacionadas con la
teoría de la complejidad computacional, la
misma es un campo de la teoría de la
computación que se enfoca en la
clasificación de los problemas
computacionales de acuerdo con su
dificultad [2].
En este contexto, el objetivo del presente
trabajo (realizado en el marco de la cátedra
de “Sistemas y Organizaciones”, primer año
de cursada) es analizar las clases de
complejidad denominadas P y NP y explicar
qué relación tiene el análisis de algoritmos
con respecto a P y NP.
Para cumplir con el objetivo propuesto, el
trabajo se estructura de la siguiente manera:
en la sección 1, se describe la Complejidad
Computacional. En la sección 2, se detallan
qué son las clases de complejidad P y NP, y
se desarrollan las características que tienen
cada una de las clases. En la sección 3, se
explica qué es el análisis de algoritmos y se
define la relación que comparten (el análisis
de algoritmos) con las clases de
complejidad P y NP. Finalmente, en la
sección 4, se desarrollan las conclusiones y
futuras líneas de trabajo.
1. Complejidad Computacional
La Complejidad Computacional (C.C)
estudia la eficiencia de los algoritmos
estableciendo su efectividad de acuerdo al
tiempo de corrida y al espacio requerido en
la computadora o almacenamiento de datos,
ayudando a evaluar la viabilidad de la
implementación práctica en tiempo y costo
[2].
La historia de la Complejidad
Computacional comienza gracias a las
máquinas de Turing, en el año 1936. La
máquina de Turing se caracterizaba por tres
elementos: [3]
Memoria: arreglo infinito (en ambas
direcciones) que en cada posición almacena
un símbolo.
Control: conjunto finitos de estados, una
cabeza lectora, un estado inicial y un
conjunto de estados finales.
Programa: conjunto de instrucciones.
El objetivo principal de la C.C se basa en la
creación de mecanismos y herramientas
capaces de describir y analizar qué tan
complejo es un algoritmo y la complejidad
intrínseca de un problema. Esto último
remarcado quiere decir que es propio o
característico del problema y no depende de
otras circunstancias [4].
2. Clases de complejidad P y NP
Los problemas que requieren de una
decisión pueden clasificarse en las
denominadas “clases de complejidad” [5].
Las clases de complejidad se definen
mediante tres conceptos: el tipo de
problema computacional, el modelo de
cómputo (el más común es la máquina de
Turing), el recurso que está siendo acotado
y la cota. Un ejemplo del último concepto
puede ser: “tiempo polinomial” o “espacio
logarítmico”, entre otros [4].
2.1 Clase de complejidad P La clase de complejidad P, es aquella que
contiene a los problemas que pueden ser
solucionados en tiempo un polinómico (esto
quiere decir, que su tiempo de cómputo está
descrito por un polinomio en el tamaño de
los datos) y sin tanta complicación por una
máquina de Turing. La clase P es una de las
más importantes dentro de la teoría de la
Complejidad Computacional, ya que, a
grandes rasgos, P contiene problemas los
cuales su solución puede ser dada por una
computadora [6].
Un ejemplo muy conocido sobre las clases
P, es el problema de determinar el árbol de
recubrimiento de peso mínimo de un grafo
(MWSR, Minimum-Wieght Spanning Tree)
es un problema que consta de, dado un
grafo G, encontrar el árbol (si existe) en G
cuyo peso sea el menor posible. Existe un
algoritmo que puede resolver este problema
conocido como algoritmo de Kruskal,
creado por Joseph Kruskal [7].
2.2 Clase de complejidad NP
Por otro lado, se puede definir a la clase de
complejidad NP, como al conjunto de
problemas que pueden resolverse en un
tiempo razonable a través de una máquina
no determinista Turing [8]. Su importancia
reside en la cantidad de problemas que
encuentra y el posible número de
soluciones, entre las cuales se compara cada
una para poder encontrar un mayor
rendimiento. Por la importancia que tiene,
con muchos esfuerzos han tratado de
encontrar algoritmos que decidan algún
problema de NP en tiempo razonable.
La clase NP tiene su clase derivada, que es
llamada NP–completo. Son aquellos
problemas más difíciles dentro de NP ya
que son intratables, no se ha encontrado
forma ni algoritmo capaz de resolver tales
problemas. Sin embargo, para uno
cualquiera de dichos problemas (dentro de
NP-completo) se encuentra un algoritmo
que lo resuelva, entonces todas aquellas
problemáticas tendrían solución en tiempo
polinomial, además la clase NP colapsaría y
se transformaría en la clase P [9]. Un
ejemplo de la clase de complejidad NP
podría ser: encontrar los factores primos
que componen un número o buscar
números primos. Ambos son problemas NP,
lo que significa que necesitamos mucho
tiempo y potencia de computación cuando
trabajamos con números muy grandes [9].
3. Análisis de algoritmos
El análisis de los algoritmos se encarga de
evaluar la cantidad de recursos informáticos
utilizados por cada algoritmo, es decir, que
tan eficiente puede ser un algoritmo a la
hora de resolver una problemática dada
[10].
Como la eficiencia es un punto fundamental
que se debe tener en cuenta al hablar de
resolver un problema, la tabla 1, permite
ver las distintas clasificaciones según el
tiempo que emplean:
O(1) Orden constante
O(log n) Orden logarítmico
O(n) Orden lineal
O(n log n) Orden cuasi-lineal
O(n2) Orden cuadrático
O(n3) Orden cúbico
O(n.a) Orden polinómico
O(2n) Orden exponencial
O (n!) Orden factorial
Tabla 1. Identifica una jerarquía con los distintos
órdenes de complejidad.
En la tabla 1 [11], se reflejan diferen-
tes funciones que determinan el uso de re-
cursos que pueden utilizar los algoritmos,
pudiendo existir infinidad de funciones. Las
mismas funciones, comparten un mismo
comportamiento asintótico.
Para contrastar la importancia que tiene la
eficiencia de los algoritmos, la tabla 2 des-
cribe el tiempo que tardaría una máquina
(por ejemplo una computadora), procesando
una entrada de n datos si dicho algoritmo
tiene una complejidad exponencial 2n:
n TIEMPO
10 » 1 décima de
segundo
20 » 2 minutos
30 > 1 día
40 > 3 años
50 = 3 570 años
100 = 4,019,693,684,133
milenios
La tabla 3, por su parte, muestra la manera
en que se ejecuta un algoritmo con una
complejidad del tipo cúbica:
Expuestas ambas tablas, se puede apreciar
que solo un algoritmo eficiente (quiere de-
cir, con un orden de complejidad bajo) pue-
de tratar grandes volumen de datos. Luego
de la tabla, es posible analizar que un algo-
ritmo puede ser muy eficiente si su comple-
jidad es de orden log n. Por otro lado, no
tan eficiente si se complejidad está dada por
n.a. y por último se puede ver que es inefi-
ciente si se trata de un algoritmos con una
complejidad de orden 2n.
Por otra parte, para resolver un problema es
necesario hacer una elección de programas
(algoritmos capaces de resolver los proble-
mas) y tal elección se realiza en base a dos
opciones:
1. Obtener un algoritmo fácil de entender,
codificar y poner a punto.
2. Un algoritmo que haga un uso eficiente
de los recursos un computador (como lo son
el tiempo y espacio), en particular uno que
se ejecute lo más rápido posible.
Para que la primera opción sea eficiente es
necesario que se utilice el programa pocas
veces. Sin embargo, cuando un problema es
recurrente y cuya solución sería utilizada
muchas veces, el costo de ejecutar el pro-
grama es más importante que el costo de
escribirlo. Es por eso que para estos casos
de problemas frecuentes y/o persistentes la
mejor opción sería la 2 ya que se haría un
mejor uso de las capacidades y recursos de
la maquina empleada para resolver aquellas
problemáticas (como podría ser una compu-
tadora) [13].
4. Conclusiones
Luego de una detallada explicación sobre la
Complejidad Computacional, cómo la mis-
ma ha surgido mediante las conocidas má-
quina de Turing, se presentaron dos tipos de
clases de complejidad: P y NP. Ambas pre-
sentan distintos tipos de grupos de proble-
máticas que tienden a tener una solución en
tiempo polinomial (o razonable), es decir
que, en computación, cuando el tiempo de
ejecución de un algoritmo (mediante el cual
se obtiene una solución al problema) es
n TIEMPO
10 = 1 décima de se-
gundo
20 = 8 décimas de
segundo
100 = 1.7 minutos
200 = 13.3 minutos
1000 » 1 día
Tabla 2. Tiempo que se demora un
algoritmo con una complejidad
exponencial de 2n (cuadrática)
Tabla 3. Tiempo que tarda un algoritmo
en procesar con una complejidad cubica
(3n)
menor que un cierto valor calculado a partir
del número de variables implicadas (gene-
ralmente variables de entrada) usando una
formula polinómica, se dice que el proble-
ma puede ser resuelto en un “tiempo poli-
nómico” [14]. Ha sido de vital importancia
remarcar el tema que trata sobre el análisis
de algoritmos, esto se debe a que para cual-
quier problema computacional, ya sea u
problema dentro del grupo P o dentro del
grupo NP, se necesitan algoritmos que lo
resuelvan en el menor tiempo posible y con
los menores recursos utilizados. Estas ca-
racterísticas del análisis de algoritmos apor-
tan al tema (problemas dentro de P y NP)
una mejor elección a la hora de optar por
diferentes soluciones a problemas plantea-
dos.
Como futuras líneas de trabajo se propone
indagar cuál es la importancia, dentro del
ámbito científico y computacional, de en-
contrar una respuesta a la problemática so-
bre si P es igual NP.
Referencias [1] S. Cook (1971)."The P vs. NP Problem".
Recuperado de la página de Internet del organismo:
http: //cort.as/-L8Zk. Accedido el 4 Jun 2019.
[2] Castro, Alberto. “Complejidad computacional”.
13 de jul. 2011. Recuperado de: http://cort.as/-
NNew. Accedido el 13 Jun. 2019.
[3] Gabriela Briceño V. (2019). “Máquina de
Turing”. Recuperado de: http://cort.as/-O9PC.
Accedido el 17 Jun. 2019.
[4] Sanchis de Miguel, Araceli. Ledezma Espino,
Agapito. Iglesias Martínez, José. Jiménez, Beatriz
García. Weber, Juan Manuel Alonso. “Complejidad
Computacional” . (S. F.). Recuperado de:
http://cort.as/-O8yd. Accedido el 21 Jun. 2019.
[5] Rosenfeld, Ricardo e Irazábal, Jerónimo. (2013).
Computabilidad, complejidad computacional y
verificación de programas.”. [Archivo PDF].
Universidad Nacional de La Plata. Editorial: Edulp.
Recuperado de: http://cort.as/-NRMW. Accedido el
23 Jun 2019.
[6] Torrealba, Víctor. (2013). “clases de
complejidad”. [Archivo PDF]. Recuperado de:
http://cort.as/-O8Fw. Accedido el 27 Jun. 2019.
[7] Arias Figueroa, Jhosimar George. (2012). “Árbol
de Expansión Mínima: Algoritmo de Kruskal”.
Recuperado de: http://cort.as/-ORVg.
Recuperado de: http://cort.as/-L8YF ISSN 2145-
549X. Accedido el 3 Jul. 2019.
[8] Maldonado, Carlos Eduardo. (2013). “Un
problema fundamental en la investigación: Los
problemas P vs. NP”. [Archivo PDF]. Revista
LOGOS. 19 Nov. 2012. Recuperado de:
http://cort.as/-O83l. Accedido el 5 Jul. 2019.
[9] Diez, Álvaro. (2016). “P contra NP el problema
del milenio, explicado de forma sencilla”. 11 junio,
2016. Recuperado de: http://cort.as/-OuqD.
Accedido el 1 Sep. 2019.
[10] Turmero, Pablo. (2017). “Análisis de
algoritmos”. [Archivo PDF]. Monografias.com.
Recuperado de: http://cort.as/-O8l4. Accedido el 10
Jul. 2019.
[11] Pinto López, Rolf Manolo. “Teoría de la
complejidad algorítmica”. Recuperado de: http:
//cort.as/-NNfl. Accedido el 13 Jul. 2019.
[12] Mayordomo, Elvira y De Miguel, Gregorio.
“Tiempo Polinómico vs Tiempo Exponencial”.
Universidad de Zaragoza. [Archivo PDF]
Recuperado de: http://cort.as/-Ovx6. Accedido el 27
Jul. 2019.
[13] Rodríguez, César Vaca (2011). “Estructuras de
Datos y Algoritmos”. 10 Sep. 2011. [Archivo PDF]
Recuperado de: http://cort.as/-Owje. Accedido el 31
Ago. 2019.
[14] Maldonado, C.E. “Un problema fundamental en
la investigación: Los problemas P vs NP”. Revista
Logos, Ciencia & Tecnología [en línea]. Disponible
en: http://cort.as/-L8YF. Accedido el 21 Ago. 2019.
[15] T.H. Cormen, C.H. Leiserson, R.L. Rivest,
C.Stein, “Introduction to Algorithms”, 3° Edición,
Cambridge, Massachusetts, England, 2009.
Accedido el 1 Ago. 2019.
Combinatoria. Una Introducción con Aplicaciones”.
3a Edición. Massachusetts. 1994. Accedido el 25 Jul
[16] Ralph P. Grimaldi, “Complejidad computacional”
en “Matemáticas Discreta y Combinatoria. Una
Introducción con Aplicaciones”. 3a Edición.
Massachusetts. 1994. Accedido el 25 Jul 2019.
[17] T.H Cormen, C.H Leiserson, R.L Rivest, C.
Stein. (2009). “Introduction to Algorithms”. 3era
Edition. Cambridge, Massachusetts, England.
Accedido el 1 Ago. 2019
Análisis de Algoritmos para determinar problemas P y NP
Autores:
Santiago Fernandez Enzo Acevedo
Cod. QR
Objetivo
Analizar las clases de complejidad P y NP y explicar qué relación tienen estas
con respecto al Análisis de Algoritmos
Una entrada de n Datos Con un algoritmo de
Complejidad Exponencial
2n
10 » 1 décima de segundo
20 » 2 minutos
30 > 1 día
40 > 3 años
50 = 3 570 años
100 = 4,019,693,684,133
milenios
La clase de complejidad P contiene problemas
que pueden ser resueltos en forma
razonablemente rápida. Por otra parte, NP es el
conjunto de problemas de búsqueda y de
optimización para los cuales se desea saber si
existe una cierta solución o si existe una mejor
solución que las conocidas
Conclusiones
• Para resolver problemas que se encuentran
dentro de las clases de complejidad P y NP, es
necesario obtener algoritmos capaces de
procesar datos de forma rápida y eficaz.
• Se remarcó la importancia de el análisis de
algoritmos sobre las clases de complejidad P y
NP ya que es necesario tener tal análisis en
cuenta para que se utilicen soluciones con un
tiempo corto de ejecución y con los menores
recursos utilizados
Este trabajo fue promovido y guiado por el equipo a cargo de Ma. Florencia Pollo-Cattaneo, con la
ayuda de Cinthia Vegega, pertenecientes a la cátedra de Sistemas y Organizaciones de la UTN-
FRBA, primer año de cursada
Se ejecuta un algoritmo que lee registros de
una base de datos, dicho algoritmo tiene una
complejidad exponencial 2n
Descripción grafica de ambas clases
de complejidad. (P y NP)
Futuras líneas
Indagar cuál es la importancia dentro del
ámbito científico y computacional, de encontrar
una respuesta a la problemática sobre si P es
igual NP
