Como no sé gran cosa de informática siempre he tenido esta duda. Qué significa exactamente eso de P=NP??

Lo he visto en Futurama, sé que es uno de los mayores enigmas de la computación, pero alguién es tan amable de explicarlo (para dummies?)

_________________

CADA VEZ QUE HACES OFF-TOPIC, UNA IDEA CPI DESAPARECE PARA VOLVER EN FORMA DE BUEY DE MAR GIGANTE. Prefiero Berberechos

Digamos que en general hay dos tipos de problemas, los P, que se pueden resolver en un tiempo determinado con una máquina determinista, esto es, que con un algoritmo se puede hacer, y los NP que se resuelven en un tiempo determinado con una máquina no determinista.

Las máquinas deterministas son, por ejemplo los ordenadores, hacen una serie de operaciones para resolver un problema por un camino, las máquinas no deterministas son capaces de resolver un problema por muchos caminos simultáneamente.

Si tratamos un problema NP en una máquina P podemos no llegar a la solucion en un tiempo polinomial, es decir, el coste temporal de la resolución es infinito a priori.

Sería importante saber qué problema es computable y cual no, para así saber que problemas podemos resolver con un ordenador y cuales no.

Si P equivaliese a NP sabríamos que los problemas que en principio pensamos que no tienen un tiempo de resolución polinómico sí que lo tienen, con un algoritmo P determinado, es decir, teniendo un problema NP hallar un algoritmo que lo solucione P.

Sólo si P=1 ( lo sientooooooo )

Corrije gato, que es "P=NP"

_________________
Depurar código es el doble de duro que escribirlo. Por tanto, si escribes el código lo más inteligentemente que te sea posible, no eres, por definición, lo suficientemente inteligente para depurarlo.

-- Brian Kernighan

* 17

veo la explicación de tecker y subo a Curiosidades Matemáticas (y físicas) en Futurama "La Pregunta del Millón" es la que trata este tema, y, además de una buena explicación, hay un enlace (por si queremos saber más) a MathWorld
Pero, en realidad, la página entera es recomendable, os recomiendo que os deis un garbeo por todos sus apartados.

_________________
Todo el mundo ama la libertad pero vive enamorado de sus cadenas
Bender, ser Dios no es fácil. Si intervienes demasiado, la gente se vuelve dependiente. Si no haces nada, pierden la esperanza. Pero si haces las cosas bien, cual cirujano o carterista, la gente no sabrá si has tenido algo que ver o no.

Como gato lo ha puesto mal y el problema es P = NP, el chiste es con N = 1

La culpa no es mía, a dos planteamientos, dos soluciones

Y ya no bueydemareo más

tecker, vaya lio que te has armado tu solo

1) Todos los problemas computables se pueden resolver en un tiempo "determinado", lo que se trata aqui es de que el tiempo es polinomico.

2) Una maquina P???? Que es eso??? Querras decir una maquina determinista. Si tenemos una maquina determinista, podemos comprobar si un resultado que nos dan es valido o no en tiempo polinomico, pero, normalmente, si tenemos que buscarlo nosotros, tengamos que recorrer todos los casos, lo que es un tiempo exponencial o factorial (mucho mas grande).

3) Todos los problemas de los que hablamos, sean P, NP o incluso peor, son computables, por definicion. Si no es computable, apaga y vamonos. Por cierto, eso no tiene nada que ver con complejidad computacional, si no mas bien con modelado con una maquina de Turing (pero eso es otro tema).

4) Con lo bien que arrancas al principio y al final te lias. Un problema NP no signinifica que sea en tiempo no polinomico, si no en tiempo polinomico no determinista. Es decir, que lo podriamos resolver en tiempo polinomico si tuvieramos infinitos ordenadores trabajando a la vez. Como se puede ver, P es un caso particular de NP para el que solo hace falta un ordenador.

Siento continuar el bueydemarismo, pero es que la palabra me ha hecho muchisima gracia por que lo de bueydemareo me ha llegado al alma.

Viene quenipintado (no por tu comentario Peti, si no por los bueyes de mar en general).

Bueno, dejemos de bueydemarear la perdiz

Yo siempre lo había oído en problemas en los que el tiempo transcurrido para encontrar una solución es mas grande que el tiempo en ejecutar la peor de las soluciones. Entonces decimos que el problema es NP.

Ok, perdón, me refería a decidible o no.

En cualquier caso, todo esto lo tengo bastante, bastante olvidado. Simplemente quería hacer una aproximación,... No he desempolvado los apuntes de computabilidad.. xd.

Por cierto, es importante lo de polinomial, puesto que sí que hay problemas NP que se pueden resolver con una máquina de Turing normal, pero el tiempo no es polinomial, puede ser factorial o exponencial...

Te pongo un problema sencillo

2 + 2 = x

Que es para ti la peor solucion? x = 5? x = 10^100? x = inf?
Como puedes "ejecutar" esa solucion?

Y hay problemas NP que pueden resolverse en tiempo polinomial.. todos los de tipo P. Ya que todos los P, como he dicho antes, son tambien NP.

Para verlo mas claro



Si se llega a demostrar algun dia que P = NP, significara que no existe ningun problema NP completo. O lo que es lo mismo, encontrar un problema NP completo implica que P es distinto de NP.

Cuando digo la peor solución quiero decir que ni tan siquiera te sale bien para la peor solución no digamos ya si la solución es la buena o más buena que la peor. Ímaginemos que en un hipotético campo de búsqueda nuestra peor solución para esta ecuación es x= 10^100; pues bien lo que quiero decir es que tardas menos en ejecutar x=10^100 que en calcular la mejor solución x=4. Aunque el ejemplo es ambiguo porqué no se trata de correcto o incorrecto como en matemáticas, sino de mejor o peor.

Tengo la impresión de que estás confundiendo la "peor solución" con el "peor caso" que se suele manejar con algoritmos que va a operar con distintas entradas de mismo número de variables (y que puede tardar más o menos en acabar dependiendo de estas variables)

_________________
Depurar código es el doble de duro que escribirlo. Por tanto, si escribes el código lo más inteligentemente que te sea posible, no eres, por definición, lo suficientemente inteligente para depurarlo.

-- Brian Kernighan

* 17

Antes que nada disculparme, es la primera vez que posteo .

Creo que os estais equivocando, segun mi libro de Analisis de diseño de algoritmos y el Brassard, la definición de P no es problema resoluble en tiempo polinomico. P es la clase de todos los problemas en los que se puede encontrar una solución en tiempo polinomico. NP es la clase de problemas que se pueden COMPROBAR en tiempo polinomico, pero solucionarlos puede hacerse en tiempo polinomico o no.

De ahi surge la Clase de problemas NP-Completos, que son sin duda los problemas NP mas dificiles y que tienen una curiosa propiedad, Si un problema es NP Completo todos los problemas de NP pueden reducirse a él.

Asi que si alguna véz se probará que P = NP, entonces todos los problemas de NP se reducirian a un problema NP-Completo, y éste que sigue estando en NP podria resolverse en tiempo polinómico. Si se probará la equivalencia, su significado seria claro. Podriamos encontrar algoritmos mejores a los actuales

de todas formas si me equivoco que me lo digan

no he entendido muy bien esto del P i NP

mi profesora de cálculo nos dijo que había contraseñas que para que un programa las pudiera hackear, se necessitaria mas tiempo que la edad del universo

tiene esto algo que ver con los NP?

_________________
- Perdón, usted hace mucho que espera?

- No, yo nunca he sido pera

P=NP? pues NPI. XD

Pues es un problema sencillo dependiendo del método de resolución.

Existen problemas que son, a priori tan sencillos y por el método sí que tienen una solución aproximada iterativamente:

PI + PI

Podemos tomar la peor sulución como 6, tomando sólo el primer dígito, la segunda peor sería 6.2, 6.28,...

Para casi todos (si no todos) los problemas de la vida real existe una solución iterativa. Creo que eso es a lo que se refieren.

A ver... Como no estoy seguro de si todo el mundo se está haciendo a la idea de qué hablamos cuando nos referimos a "tiempo polinómico", voy a poner un ejemplo bastante típico: ordenación de una serie de números (ordenación y búsqueda son arquetípicos y nos machacan con eso parte de la carrera).

[LADRILLO VA]
Imaginemos que tenemos una serie de números (10, 20, 100, 1000, los que sean), que nos los dan desordenados (supuestamente) y que los queremos poner por orden. Uno de los algoritmos más sencillos para un caso como éste es la "ordenación de burbuja" (bubble sort), que se llama así porque los números más pequeños van "subiendo" y los más grandes "bajando" en la lista de números que tenemos, según vamos haciendo pasadas por ella.

Primero va una descripción en "pseudocódigo" del algoritmo (luego la explico):



El ejemplo es bastante sencillo de entender. Tenemos un procedimiento al que llamaremos ordenar_burbuja al que le pasamos una lista. Esta lista tiene n elementos numerados del 1 al n[/b], y para acceder a cada uno de ellos individualmente usaremos la notación [i]lista[k], siendo k el índice de ese elemento dentro de la lista. La estructura para ... hasta ... hacer es un tipo de lo que llamamos "bucle", es decir, una estructura repetitiva. En particular, lo que hace es repetir el trozo de código que contiene, asignando valores desde 1 hasta tamaño(lista)-1 (es decir, hasta n - 1) a una variable que vamos a llamar x. Estos valores los asignará en orden creciente (1, 2, 3, etc). Además, usaremos una señal, ordenado, para saber si la lista está ordenada y podemos dejar de hacer repeticiones.

La idea entonces es simple. Asumimos de entrada que la lista está ordenada (ordenado = verdadero). Pasamos entonces a ir comparando cada elemento con el que le sigue, usando el bucle para eso. Si por casualidad encontramos en el recorrido que al menos dos de ellos están al revés (el mayor está antes que el menor), los intercambiamos y marcamos ordenado = falso, de manera que cuando acabemos de hacer esta pasada de comprobaciones, empecemos de nuevo, para asegurarnos que esta vez *sí* está todo bien ordenado.

Ejemplo del aspecto que tendría una de estas listas según avanza el algoritmo al principio de cada uno de los ciclos:



Como se ve, los números más pequeños van "gravitando" hacia el principio de la lista, y los más grandes hacia el final.

Ahora, lo interesante: ¿cómo predecimos el tiempo que va a costarnos hacer todo esto? Vamos a asumir que cada operación (una asignación, una comparación, el intercambio de dos valores) nos va a costar una "unidad de tiempo" (que puede ser 1 segundo, 1 millonésima de segundo, semana y media, da igual...), y ahora pasamos a contar el número de operaciones que hacemos . Esto supone un problema, porque a priori no sabemos cuántas veces se va a repetir el bucle (ya que depende de lo desordenada que esté la lista inicialmente), o cuántas veces se va a repetir el intercambio de valores (ya que sólo sucede si dos valores comparados están desordenados, claro). Es por esto que normalmente los valores que nos interesan son el "mejor caso" y (especialmente) el "peor caso".

Empecemos analizando el interior del bucle para. Vemos que hay cuatro instrucciones potenciales: asignar un valor a x, la comparación, el intercambio de valores, y poner ordenado a falso. Es decir, por cada pasada del bucle ejecutaremos de 2 a 4 instrucciones (dependiendo de si la condición de la comparación se cumple o no). Vamos a tomar el peor valor (4).

Segundo, hemos determinado que el bucle para se va a ejecutar siempre "n-1" veces, así que el bucle va a tardar siempre entre 2*(n-1) y 4*(n-1) unidades de tiempo en ejecutarse.

Por último, nos queda saber cuántas veces va a ejecutarse ese bucle. Eso, como decíamos, depende de lo "bien" o "mal" ordenado que esté la lista inicial. El mejor caso sería claramente que nos pasasen la lista ya totalmente ordenada, ya que pasaríamos una vez por ella, comprobándolo todo, y al llegar al final veríamos que nada ha cambiado y que podríamos salir sin más, todo ello en 2(n-1) unidades de tiempo. El peor caso sería que nos hayan dado una lista en que no se repita ningún número y el más pequeño de todos ellos estuviera al final del todo, independientemente de lo bien o mal ordenado que esté el resto de la lista. ¿Por qué? Dado que cada elemento sólo se mueve un máximo de un puesto por cada ciclo del bucle, si el más pequeño está al final, habrá que ejecutar el bucle n-1 veces para moverlo hasta donde le corresponde (el primero de la lista), con lo cual habrá que multiplicar lo que tenemos hasta ahora por (n-1), de nuevo.

Resumiendo: nuestro algoritmo se ejecutará entre 2*(n-1) (mejor caso) y 4*(n-1)^2 (peor caso) veces. Dado que el tiempo para el mejor caso depende de un número relacionado con el número de elementos de la lista, decimos que la cota inferior tiene orden lineal. El peor caso depende de un número relacionado con el cuadrado de elementos que componen la lista, así decimos que la cota superior es de orden cuadrático. En notación algorítmica escribiríamos esto como O(n^2), despreciando las constantes multiplicativas asociadas.

Este análisis temporal es importante porque nos permite comparar soluciones a un problema sin necesidad de hacer pruebas exhaustivas, que aparte de costosas (en tiempo) podrían dar lugar a resultados engañosos. Por ejemplo, un algoritmo podría ser mejor que otro hasta un "n" determinado, pero ser peor de ahí en adelante. Si nos aburrimos de comparar en "n-1" y luego aplicamos el primer algoritmo para "n^2" elementos, la hemos jodido

En cualquier caso, lo importante aquí es que hemos obtenido un polinomio que nos dice cuánto tiempo va a tardar nuestro programa en resolver el problema.
[/LADRILLO]

Es más, dado que nuestro programa puede implementarse en una máquina determinista (nuestro ordenador), entonces cae dentro del conjunto P. Si hubiéramos tenido que usar una solución no determinista para nuestro problema, pero una con tiempo polinómico de resolución, entonces hablaríamos de un problema que cae fuera de P (pero dentro de NP).

Edit: joder con el cortar+pegar

_________________
Depurar código es el doble de duro que escribirlo. Por tanto, si escribes el código lo más inteligentemente que te sea posible, no eres, por definición, lo suficientemente inteligente para depurarlo.

-- Brian Kernighan

* 17

En otro mensaje, para no tocar más el ladrillo

[SEMILADRILLO]
Un caso interesante es el de la comprobación de la primalidad de un número. Hasta hace poco (2002) se pensaba que era un problema de clase NP, pero ha resultado ser que es estrictamente de clase P (¡bien!). Sin embargo, el verdadero problema viene con los problemas que llamamos NP-completos.

Como comentaban antes, los NP-completos podríamos clasificarlos como los "problemas NP más difíciles", en el sentido de que es el subconjunto de NP que tiene la mayor probabilidad de estar fuera de P. ¿Qué tiene que cumplir un problema NP para ser NP-completo?

a) estar en NP (¿parece obvio, no?)
b) ser NP-hard

¿Y eso de NP-hard? Si cualquier otro problema NP puede ser "reducido en tiempo polinómico" a nuestro candidato, entonces es NP-hard. Con "reducir" nos referimos a transformar un problema en otro. Y conque lo sea en tiempo polinómico nos referimos a que esa transformación debe poder ser computada por una máquina de Turing en tiempo polinómico.

Muchos polinomios veo yo por aquí, ¿no?

En resumen: hay una serie de problemas que digamos forman el "núcleo duro" de los NP, que son los NP-completos. Todos los problemas de NP son equivalentes de una u otra manera a estos NP-completos. Con el tiempo se ha descubierto que algunos NP en realidad son P, pero los NP-completos siguen invictos (el más estudiado de ellos es el problema del viajante). Si algún día se descubriese que uno solo de los NP-completos es en realidad un P, entonces podríamos decir que P=NP.
[/SEMILADRILLO]

_________________
Depurar código es el doble de duro que escribirlo. Por tanto, si escribes el código lo más inteligentemente que te sea posible, no eres, por definición, lo suficientemente inteligente para depurarlo.

-- Brian Kernighan

* 17

Que yo sepa decidible y computable es lo mismo.



No es sólo que haya problemas NP que se pueden resolver en una máquina de Turing "normal". TODOS los problemas NP se pueden resolver en una máquina de Turing "normal" (pero no todos en tiempo polinomial).

Me parece que esto no es correcto. Se conocen muchísimos problemas NP-completos:

http://en.wikipedia.org/wiki/List_of_NP ... e_problems

La cuestión es conseguir saber si alguno de ellos, además de ser NP, es también P. Si se consigue demostrar que uno de ellos es P entonces P=NP. Si se consigue demostrar que alguno de ellos no está en P entonces P y NP serán distintos.

No entiendo muy bien la diferencia que intentas remarcar. Creo que las dos cosas son lo mismo.



Sí, exacto.



No basta con que puedan reducirse a él. Tienen que poder reducirse en tiempo polinómico.



Esto ya es así (aunque P y NP no fueran iguales) por la propia definición de NP-completo.

Las máquinas de Turing deterministas y no deterministas tienen exactamente la misma capacidad (son modelos equivalentes). Pueden resolver exactamente los mismos problemas. Lo que no se sabe si es cierto o no es si las MT no deterministas son más rápidas. Ese es el problema P=NP. ¿Lo que puedo hacer rápido con una MR no determinista lo podría hacer también rápido con una determinista? No lo sabemos.



En ese caso tendríamos un problema NP, pero no sabemos si está en P o no (si lo supiéramos probablemente solucionaríamos la cuestión P=NP).

Sí, puede tener bastante que ver. Muchos algoritmos actuales de encriptación se basan en la dificultad del problema de fatorizar un número entero (es decir, hallar sus factores primos). Este problema no se sabe si está en P o en NP, si es NP-completo o no. Si se consiguiera determinar, podría ser un buen avance hacia la resolución de ¿P=NP?

Exacto, exacto. También, si se descubriera que uno solo e los NP-completos no está en P entonces se tendría la solución (en ese caso P y NP serían distintos). Por eso los problemas NP-completos son tan importantes.

En la wikipedia he encontrado un ejemplo de problema NP-completo que es muy sencillo de comprender y que puede aclarar estas cosas:

http://en.wikipedia.org/wiki/Subset_sum_problem

Simplemente, nos dan un conjunto de enteros y hay que determinar si podemos coger algunos de ellos cuya suma sea cero.

Lógicamente, si nos dan una posible solución (una serie de números) podemos comprobar rápidamente (en tiempo polinómico) si realmente es una solución (basta con sumar los números y ver si son cero). Entonces el problema es NP (podemos comprobar una solución en tiempo polinómico). Pero si queremos ponernos a buscar una solución, ¿qué tenemos que hacer? Parece que casi lo único que se puede hacer es ir cogiendo cada subconjunto posible de números y "probar" con ellos. Como hay 2^n subconjuntos de un conjunto de n elementos, el tiempo de esa solución sería exponencial (que es mayor que polinómico).

Ahora bien, lo que no se sabe es si hay otra manera mejor (más rápida, en concreto en tiempo polinomial) de resolver este problema. Si se supiera, tendríamos solucionada la cuestión ¿P=NP?

Por supuesto. Son equivalentes en cuanto a potencial de cálculo pero difieren (a priori) en velocidad. Mientras no se demuestre lo contrario (es decir, mientras ¿P=NP? siga siendo incógnita), habrá problemas que en P se resuelven en tiempo exponencial pero en NP se resuelven en polinómico. Perdona si hago un poco uso de licencias al escribir.



De nuevo, licencia. Por ahora se asume que P y NP-completo son disjuntos (y la opinión mayoritaria es que lo son, aunque no se pueda decir estrictamente, claro), así que por ahora creo que nos podemos permitir un poquito hablar de esta manera.



Exacto. Para los problemas NP-Completos sólo se pueden dar soluciones óptimas (por ahora) recorriendo las soluciones de forma exhaustiva. Hay soluciones parciales, como por ejemplo implementar sólo un caso particular del problema que sepamos que se ajuste y que sea de clase P, o aproximaciones (numéricas, probabilísticas, eurísticas, genéticas) que nos den un valor de solución dentro de un rango aceptable, aunque no sea el óptimo.

_________________
Depurar código es el doble de duro que escribirlo. Por tanto, si escribes el código lo más inteligentemente que te sea posible, no eres, por definición, lo suficientemente inteligente para depurarlo.

-- Brian Kernighan

* 17

Totalmente de acuerdo en todo Sólo eran matizaciones porque a veces en estos temas se hacen interpretaciones erróneas (algo semejante pasa con el teorema de incompletitud de Gödel o con la tesis de Church-Turing, que hay cada cosa por ahí que...).

No todos los problemas son decidibles, hay problemas para los que la máquina de Turing no para. Precisamente es una parte de la asignatura de computabilidad, demostrar si la maquina para (del verbo parar) para decidir si una palabra pertenece o no a un lenguaje.