Embed Size (px)
Citation preview
Joan Manuel Vidal Encarnación 13-0980
Juan Erasmo Rivera Garcia 13-0992
Problemas P y NP
Artículo: Problemas P y NP
Joan Manuel Vidal Encarnación, Juan Erasmo Rivera García
Mat. 13-0980 Mat. 13-0992
Prof. Dra. Ing. Rina Familia
Teoría de Autómatas y Lenguajes Formales
Universidad Iberoamericana (UNIBE)
Santo Domingo, República Dominicana
24 de Febrero de 2014
Breve resumen acerca del contenido de este articulo
En este estudio que hemos realizado, estaremos mostrando los problemas P y NP, así
como varios ejemplos de los mismos. El propósito de este artículo, es enfatizar los tipos
de problemas y las posibles soluciones de los mismo, adicional ver si alguien entiende
de forma muy sencilla como explicar los problemas NP y sus soluciones, que
conllevaría a ganar 1 millón de dólares que propone el Instituto Clay por lograr esta
hazaña.
Por nuestra parte también estaremos explicando que son los problemas P y no tan
directamente, pero también estaremos explicando los problemas NP que componen un
universo tan directo y difícil a su vez. Gracias a la solución del problema P se descubrió
como crear el computador, se estima que al descubrir el problema NP se puedo lograr
algo superior, ya que es mucho más complicado este tipo de problemas.
Introducción
En este tema estaremos presentando, el estudio realizado a los tipos de complejidad P
(algoritmo determinístico polinomial) y NP (algoritmo no determinístico). Hemos
realizado esta investigación ya que forma parte primordial de la inteligencia
computacional y nos estará ayudando a la solución lógica de muchos problemas, así
como también tratar de encontrarle una explicación y solución a la complejidad tipo NP.
Cabe resaltar que al igual a este hay muchas investigaciones realizadas por otros
investigadores en el campo, tanto así que hay un instituto que da como premio 1 millón
de dólares al que logre resolver los problemas de tipo NP.
A continuación se estarán mostrando toda la información que estaba disponible al
momento de crear este artículo (se estarán presentando versiones de diferentes
fuentes), así como algunos ejemplos de los problemas que se pueden presentar:
Problemas P y NP
La Complejidad Computacional es una rama de la teoría de la computación que
estudia, de manera teórica, la complejidad inherente a la resolución de un problema
computable, comúnmente se estudia el tiempo y el espacio, pero para realizar esto
primero debemos introducir la noción del problema.
La complejidad computacional considera globalmente todos los posibles algoritmos
para resolver un problema dado.
Existen diferencias entre los problemas que pueden ser resueltos por un algoritmo en
tiempo polinómico y los problemas para los cuales no se conoce ningún algoritmo
polinómico, es decir no es polinómico.
Tiempo polinomial
En computación cuando el tiempo de ejecución de un algoritmo es menor que un cierto
valor calculado, obviamente usando una formula polinomial como por ejemplo
logarítmica, lineales, cuadráticas o cubicas, se dice que dicho problema se puede
resolver en un tiempo polinómico.
Clasificacion de los Problemas
Los problemas matematicos los podemos dividir en dos grupos:
Problemas indecidibles: Aquellos que no se pueden resolver mediante un
algoritmo.
Problemas decidibles: Aquellos que cuentan al menis con un algoritmo para su
cómputo.
Sin embargo, un problema decidible puede no ser solucionado por un computador,
porque el algoritmo requiere un numero elevado de operaciones para resolverlo. Esto
permite separar los problemas decidibles en dos.
Problemas Tratables
Son los problemas que cuentan con al menos una solucion polinomial.
Ejemplo: Todos los algoritmos a los que se la ha podido establecer su tiempo de
ejecución.
Problemas Intratables
La cuestión de la inclusión estricta entre las clases de complejidad P y NP es uno de
los problemas abiertos más importantes de las matemáticas. El Instituto Clay de
Matemáticas (Cambridge, Massachusetts) premia con un millón de dólares a quién sea
capaz de lograr la resolución de esta conjetura. Alguien en una ocasión me explicó éste
problema con un ejemplo muy sencillo de entender. Me apostaría lo que fuese a que la
mayoría de los lectores de aquí no sabrían resolver manualmente una raíz cuadrada,
aunque no me cabe ninguna duda a que todos sabrían elevar un determinado número
al cuadrado. Llegamos a la conclusión que resolver una raíz cuadrada (que existe un
método muy laborioso) es más complicado o lento que la operación inversa.
Si un problema nos pide que comprobemos si un número determinado X es la raíz
cuadrada de Z podríamos resolverlo de dos formas:
Calculando la raíz de Z y comparando con X (proceso lento y engorroso)
bien, elevando al cuadrado a X y comparando con Z (simple multiplicación X·X)
La conclusión que sacamos de éste sencillo ejemplo es que en algunos problemas
comprobar la solución es más eficiente que calcularla. La complejidad de la función
“elevar al cuadrado” es más simple que calcular la raíz cuadrada. ¿Qué tiene que ver
No admiten
algoritmos
razonables
Problemas
Intratables
Problemas
Tratables
Admiten algoritmos
razonables
todo esto con P=NP? Pues bien, P es la clase de complejidad que contiene problemas
de decisión que se pueden resolver en un tiempo polinómico. P contiene a la mayoría
de problemas naturales, algoritmos de programación lineal, funciones simples,... Por
ejemplo la suma de dos números naturales se resuelven en tiempo polinómico (para
ser más exactos es de orden 2n). Entre los problemas que se pueden resolver en
tiempo polinómico nos encontramos con diversas variedades como los logarítmicos
(log(n)), los lineales (n), los cuadráticos (n2), los cúbicos (n3),... Volviendo al ejemplo
principal llegamos a la conclusión que la función de elevar al cuadrado está contenida
en la clase P.
La clase de complejidad NP contiene problemas que no pueden resolverse en un
tiempo polinómico. Cuando se dice que un algoritmo no puede obtener una solución a
un problema en tiempo polinómico siempre se intenta buscar otro procedimiento que lo
consiga mejorar. Frente a los problemas contenidos en P tienen métodos de resolución
menos eficaces. Podemos ver que la operación de calcular la raíz cuadrada se
encuentra contenida en esta clase.
Si nos resulta sencillo encontrar una solución para un determinado problema, sabemos
comprobar si la solución es cierta (simplemente comparar), por lo que P es un
subconjunto de la clase NP. La gran cuestión es si ocurre lo mismo a la inversa, es
decir, si tengo un problema que sé comprobar fácilmente si un resultado es una
solución, ¿sé calcular una solución sencillamente? ¿Todo problema se puede resolver
en tiempo polinómico? Si alguien conoce la respuesta que se dirija al Instituto Clay y
recoja su millón de dólares.
Las clases P y N P
Son clases de problemas de decisión. La N de N P viene de la generación no
determinística y la P de la verificación polinomial.
Un problema de decisión pertenece a la clase P si existe un algoritmo
determinístico polinomial, en el largo de la entrada, que lo resuelve.
Un algoritmo determinístico es esencialmente una máquina de Turing.
Un problema pertenece a la clase N P si es que es posible generar una solución.
Algunos ejemplos de problemas de decisión en la clase P:
Dado un grafo (V, E), ¿es d la distancia mínima entre el nodo v1 y el nodo v2?.
Dada una lista de números L, ¿es la lista L 0 una ordenación ascendente de L?
El proceso de generación y verificación puede ser aclarado con el siguiente esquema:
Los problemas P y NP se relacionan con los problemas de decisión que requieren una
respuesta de SI o No.
Los problemas P pueden resolverse en Complejidad Polinómica por una maquina
determinista que se subdivide en Conjunto P y Conjunto Co-P, en la primera la
respuesta es positiva y en la segunda la respuesta es negativa, ambas pueden ser
verificadas rápidamente.
Sus aplicaciones son el Algoritmo Dijkstra, el cual encuentra un
camino corto desde un origen. Y también se utilizan en el Ciclo
Euleriano que recorre cada vértice solo una vez en un grafo.
Los problemas NP pueden resolverse en
Complejidad no polinómica por una maquina no
determinística y se aplican en Camino Hamiltoniano, es
decir, que pasa por cada vértice de un grafo una vez.
Tiempo polinómico por medio de una información extra
(certificado) por ejemplo, verificar si un número es
factorizable y dar un factor de él mismo.Diagrama de Euler para problemas P, NP, NP-completo y NP-duro
Un problema es de tipo P si existe un algoritmo polinomial que lo resuelve, dicho de
forma intuitiva "si es fácil de resolver". Por ejemplo, cuando sales de viaje normalmente
quieres saber cuáles son los caminos que puedes tomar para ir de tu hotel a varios
puntos de la ciudad. Este problema se resuelve fácilmente con el algoritmo de Dijkstra
en O(n²) operaciones, por lo tanto es de tipo P.
Un problema es de tipo NP si existe un algoritmo polinomial que es capaz de verificar
una solución propuesta. Dicho intuitivamente, NP son los problemas que son "fáciles de
comprobar". Todo problema P es también NP, pero parece ser que no es al revés.
Continuando con el ejemplo anterior, en el mapa tienes marcado n lugares diferentes
de la ciudad y quieres saber si existe un camino que pase por todos esos lugares
exactamente una vez (sin repetición). Este problema es muy fácil de comprobar, si yo
te propongo una solución tú rápidamente puedes comprobar en tan solo O(n)
operaciones que el camino que yo propuse efectivamente pasa una sola vez por los n
sitios. A pesar de que es fácil de comprobar, nadie sabe cómo resolverlo facilmente.
Todos los algoritmos que se han descubierto para este problema no son esencialmente
mejores que una búsqueda por fuerza bruta (pero nadie ha comprobado que no exista
un algoritmo polinomial para resolverlo). Este problema se conoce como el problema de
Camino Hamiltoniano.
Algunos ejemplos de problemas pospuestos.
El premio por resolver alguno de estos problemas es de un millón de dólares. La
descripción del Instituto Clay sobre el problema P versus NP es más o menos la
siguiente:
"Supongamos que estás organizando el alojamiento para un grupo de cuatrocientos
estudiantes universitarios. El espacio es limitado y sólo cien de los estudiantes recibirán
lugares en los dormitorios. Para complicar las cosas, el Decano te ha proporcionado
una lista de parejas de estudiantes que presentan incompatibilidad entre sí, y pidió que
ningún par de la lista aparezca en la distribución final."
Este es un ejemplo de lo que los científicos en computación llaman un problema NP,
porque es fácil comprobar si una determinada lista de cien estudiantes propuestos es
satisfactoria (es decir, ningún par tomado de lista aparece en la lista de
incompatibilidades entregadas por el decano). Sin embargo la tarea de generar una
lista desde el principio parece ser tan difícil, como completamente impracticable.
De hecho, el número total de maneras de elegir un centenar de estudiantes
procedentes de los cuatrocientos solicitantes ¡es mayor que el número de átomos en el
universo conocido! Así que ninguna civilización futura podría esperar construir un
supercomputador capaz de resolver el problema por fuerza bruta, es decir, revisando
cada posible combinación de 100 estudiantes.
Sin embargo, esta aparente dificultad sólo podría reflejar la falta de ingenio del
programador. Uno de los problemas pendientes en ciencias de la computación es
determinar si existen problemas cuya respuesta puede ser rápidamente verificada, pero
que requieren un tiempo imposiblemente largo para resolver, por cualquier
procedimiento directo. Problemas como el mencionado al principio parecen ser de este
tipo, pero hasta ahora nadie ha logrado probar que algunos de ellos son realmente tan
difíciles como parecen, es decir, que realmente no hay forma viable de generar una
respuesta con la ayuda de un computador. Stephen Cook y Leonid Levin formularon en
1971, de forma independiente el problema de P versus NP.
La pregunta, en esencia, que propone el problema P versus NP es la siguiente:
"Supongan que la solución a un problema puede ser verificada rápidamente con un
computador. Entonces, ¿es posible que la solución en si misma pueda ser computada
rápidamente?"
Ustedes dirán, ¡estos son problemas de los matemáticos, o de los computólogos y si se
resuelven no tiene ninguna importancia práctica. Les sugiero que lo reconsideren,
porque un problema matemático, más abstracto aún, propuesto hace unos 110 años
atrás, llevó a la creación del computador, y generó todos los adelantos tecnológicos
que disfrutamos en la actualidad gracias a la informática.
Un poco de analogía y sobre la importancia del problema P y NP:
Cada mes se publican en ArXiv artículos que dicen resolver el problema. Algunos dicen
que P=NP, otros que P≠NP, etc. La diferencia estuvo en que este artículo en particular
había pasado todos los exámenes que utilizan los teóricos en complejidad para
discriminar los artículos serios. Además, este estaba escrito por una persona conocida,
y cuando había enviado una versión preliminar a un grupo selecto de científicos, uno
de los principales, el mismo descubridor del problema y ganador del premio Turing,
Stephen Cook, había escrito en respuesta "esto parece un esfuerzo serio" (del inglés
this looks like a serious effort). Esto había motivado al resto y puso a funcionar una
máquina bien aceitada de colaboración científica inigualable en la red. Como lo dijo
Dick Lipton, "lo que antes se hacía en meses, ahora por Internet lo hacemos en días".
Para saber como terminó toda la historia recomiendo el post anterior de Alejandro
donde tienen todos los enlaces. Aquí me voy a concentrar en la definición e importancia
de P vs NP.
A continuación un pequeño repaso del problema. Antes que nada este es considerado
el problema principal, más importante, de las ciencias de la computación. Básicamente
el problema es "para ciertos problemas, lo mejor que podemos hacer es una búsqueda
bruta", o como escribe Lipton "para ciertos problemas el algoritmo más obvio es el
mejor". NP como sabemos quiere decir "tiempo polinomial no-determinístico", y P
"tiempo polinomial determinístico". Entonces los problemas o lenguajes con algoritmos
que corren en tiempo polinomial están en P, y los problemas con algoritmo en tiempo
polinomial no-determinístico en NP.
Una caracterización más fácil de entender de problemas en NP es la siguiente: Sea A
un algoritmo que tiene dos entradas, x que representa una instancia de un problema L
(e.g. SAT, TSP, etc), y c que representa una solución al problema. Entonces L están en
NP si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A y
existe un c tal que A(x,c)=1, i.e. que c sea una respuesta válida al problema.
Generalmente a c se le llama solución, certificado, testigo o simplemente prueba, i.e.
una prueba de que x tiene solución. La misma caracterización se puede hacer para P,
pero esta vez el algoritmo no tiene una prueba c. Entonces decimos que L está en P si
y solo si existe un algoritmo determinístico que corre en tiempo polinomial A tal que
A(x)=1.
La gran diferencia está en el certificado. Los algoritmos para lenguajes en P determinan
una solución, mientras que los algoritmos para lenguajes en NP verifican una solución.
Una buena analogía es: si yo resuelvo un problema matemático por mi mismo (está en
P), o estoy verificando la solución de otra persona (en NP). Entonces, la diferencia
radica en que estamos comparando un proceso de determinar una solución a un
problema contra un proceso de verificación de una solución ya dada para un problema.
P vs NP en términos computacionales se refiere a cotas inferiores de problemas NP-
completos. La conjetura es que para estos problemas no existe un mejor algoritmo que
el de fuerza bruta, i.e. P≠NP. La mayoría de los científicos creen que esto es cierto, y
de ahí surgen un montón de alternativas para resolver problemas NP-completos como
Búsqueda Local, Algoritmos Genéticos, etc. Y la eficiencia de estos métodos está en
que pueden verificar soluciones en tiempo polinomial.
En mi humilde opinión, una prueba de que P≠NP no cambiaría mucho las cosas porque
todo lo que hacemos ahora, lo hacemos en función de que P≠NP. Por ejemplo,
asumimos la existencia de funciones de una vía en criptografía ¿Entonces de que nos
sirve una prueba de eso? Una prueba no solo nos dice si una hipótesis es falsa o
verdadera, sino que al mismo tiempo ganamos mucha información acerca del problema
mismo. De una prueba de P≠NP podemos descubrir muchas conexiones entre áreas
de conocimiento u objetos que creíamos desconectados en nuestra teoría. Eso tiene
mucho más valor que una respuesta de falso o verdadero. Esto es lo que está
ocurriendo con la prueba de Deolalikar.
En el aspecto filosófico, P vs NP hace la siguiente pregunta: ¿Puede la creatividad ser
automatizada? Si yo escribo un libro en el que trabaje 1 año, y lo mando a un periódico
para que un crítico lo lea, y la destruye completamente en 2 semanas, ¿Qué es más
difícil, escribir el libro o criticar el libro? Intuitivamente el proceso creativo es más
complejo y requiere más tiempo, pero hasta que no tengamos una prueba que indique
sin duda alguna nunca sabremos, por la misma razón que expuse en el párrafo de
arriba. Simplemente por la curiosidad del hombre, tenemos que saber (esto lo dijo
David Hilbert).
También la misma pregunta se extiende a otros ámbitos como la física. La visión de las
ciencias de la computación y una parte de la comunidad de físicos, es que toda nuestra
realidad física es computable. Desde la evolución de los seres vivos, hasta la formación
de galaxias. Todo es visto como un proceso que dado una entrada genera un salida.
Entonces salen preguntas como ¿Qué tan complejo es el plegado de proteínas? ¿Qué
pasa con la información y la energía en un hoyo negro que se disipa en forma de
radiación de Hawking? Muchas de estas preguntas están siendo respondidas por
técnicas de ciencias de la computación. Por ejemplo, sabemos que si P≠NP entonces
no podemos viajar en el tiempo, o no podemos movernos más rápido que la luz, y otras
conexiones más extrañas. Aun así, estás conexiones dan evidencia a favor de que
P≠NP, o no.
Así que P vs NP no solo se refiere a problemas que solo interesan a las ciencias de la
computación. Se refiere también a problemas fundamentales de otras ciencias.
Inclusive podría decirse que es una de las preguntas más fundamentales de las
matemáticas. Saber si podemos encontrar pruebas eficientemente nos da conocimiento
de cómo resolver otros problemas muy difíciles como la Hipótesis de Riemann. Es por
ello que el Clay Mathematics Institute lo pone en su lista de problemas fundamentales.
Resultados
Los resultados obtenidos en esta investigación nos han inducido a dar una definición
completa de los problemas P y NP con el siguiente gráfico.
Conclusión
El primer problema natural que se demostró que es completo NP fue el problema de
satisfacibilidad booleana. Este resultado fue demostrado por Stephen Cook en 1971, y
se lo llamó el teorema de Cook. La demostración de Cook de que la satisfacibilidad es
un problema NP-completo es muy complicada. Sin embargo, después de que este
problema se demostrara que es NP-Completo, es fácil demostrar que muchos otros
problemas pertenecen a esta clase. Por lo tanto, una amplia clase de problemas en
principio inconexos son reducibles unos a otros, y por lo tanto resultan en "el mismo
problema" -- un resultado profundo e inesperado.
Bibliografía
Baier Aranda, J. (n.d). Introducción a la Complejidad Computacional. Disponible en:
http://web.ing.puc.cl/~jabaier/iic2212/complejidad.pdf
Díaz Cortés, E. (2010). P versus NP. Disponible en: http://www.lnds.net/blog/2010/08/p-
versus-np.html
Jiménez, A. (2006). P versus NP. ¿Nunca lo entendiste? Disponible en:
http://www.xatakaciencia.com/matematicas/p-versus-np-nunca-lo-entendiste
Universidad del Valle de Guatemala (n.d.). Problemas P y NP Completo. Disponible en:
http://streaming.uvg.edu.gt/mediawiki/images/4/4f/MapaconceptualPNP4.jpg
Villaga, M. (2010). La Importancia de P vs NP. Disponible en:
http://computacioncuantica.blogspot.com/2010/08/la-importancia-de-p-vs-np.html
