Dudas simples de matemáticas

#67

Este articulo de Scott Aaronson lo explica mejor de lo que yo pueda hacerlo, pero en ingles. Si quieres leete el suyo (mas divulgativo) y el mio (me ha quedado un poco demasiado tecnico), y comenta si algo te falla.

P=NP es un problema emblematico de la computacion teorica. La idea es clasificar los problemas segun su "dificultad" de resolver con un algoritmo. Hay muchas clases de problemas (Co-NP, PSPACE, BQP, etc.) y casi no hay ningun gran teorema resuelto en ninguna de las clases, pero como ya digo, P=NP es lo mas emblematico.

Para empezar, hay que definir lo que es un problema de optimizacion y de decision.

Definimos un problema de optimizacion como una tupla <Iq, Sq, fq, optq> donde:
Iq es el conjunto de instancias posibles (todos los posibles inputs del problema).
Para cada x en Iq (para cada input) Sq(x) es el conjunto de soluciones posibles para ese input.
fq es una funcion definida para cada input y cada solucion posible de ese input.
optq es como vamos a optimizar esa funcion (minimizar o maximizar?).

Asi dado un input x la idea es de todos los y en Sq(x) encontrar el que minimize o maximize (segun optq) fq(x,y).

Un problema de decision es un problema de optimizacion donde fq es 0 o 1. Son problemas del tipo "Existe alguna ruta para la cual este camion consuma menos de X gasolina?" (No hace falta encontrar la mejor ruta!)

Se dice que un problema de decision esta en P si existe un algoritmo que dada cualquier instancia x de Iq que tenga solucion, encuentre y en Sq(x) en un tiempo polinomico en la longitud (en bits) de x, y cualquier instancia x de Iq que no tenga solucion, responda que x no tiene solucion en un tiempo polinomico en la longitud (en bits) de x. Tiempo polinomico quiere decir que el algoritmo hara como maximo, sea cual sea x (siempre y cuando la longitud sea menor o igual que n) una constante multiplicada por n elevado a un numero fijo. Este tipo de problemas son buenos, porque si la longitud de x aumenta un poco, el numero de pasos que hara el algoritmo aumentara de manera controlada. Por ejemplo la multiplicacion de matrices es P (dadas A y B matrices mxm encontrar C = A.

Se dice que un problema de decision esta en NP si existe un algoritmo tal que para cualquier x una instancia que tenga solucion de Iq existe una h, una "pista" (hint) de longitud acotada por un polinomio funcion de la longitud de x, tal que el algoritmo es capaz de decir en tiempo polinomico si x tiene solucion, y que para cualquier x que no tenga solucion, cualquier pista que le des resultara en una respuesta negativa en tiempo polinomico. Vale, esto es muy lioso dicho asi sin formulas. La idea es realmente "sencilla". Ponle un problema tipico NP, el problema del viajante (lo que he comentado arriba, existe una ruta que pueda seguir este comerciante que le haga gastar menos de x gasolina?). Este problema esta en NP porque si al darle la matriz de puntos y distancias le das como pista una posible ruta es muy facil hacer un algoritmo que te diga si la matriz es correcta o no.

Se dice que un problema esta en P si se puede "resolver rapido", y esta en NP si se puede "comprobar la solucion" rapido.

Como analogia, un algoritmo de este tipo es como un profesor de matematicas muy inteligente. Si tu le traes un teorema y le dices que lo demuestre, quizas no sea capaz de hacerlo. Pero si le traes una demostracion hecha por ti rapidamente te dira si es correcta o no.

Como ves, esta claro que si un problema esta en P entonces tambien esta en NP, ya que si puedes resolverlo rapido cualquier pista que le des sera redundante. La pregunta es, y al reves tambien es asi? Fijate que hay dos preguntas aqui. Una es, "es lo mismo ser NP que ser P?" y la otra es "Como podemos resolver estos problemas NP de manera P?" Hay problemas que son lo que se llama NP-completo, eso es que cualquier problema NP puedes reformularlo y reinterpretarlo como uno de estos problemas. Si fueramos capaces de hacer un algoritmo que resuelva uno de estos problemas en tiempo polinomico, entonces P=NP.

Hay argumentos tanto a favor como en contra de P!=NP. Yo creo que P!=NP y de hecho como dice Scott Aaronson creo que no hay manera de resolver un problema NP-completo en tiempo polinomico usando una cantidad modesta de energia (para evitarnos viajes en el tiempo, irnos a la velocidad de la luz y volver, cosas asi). Pero esto es todo especulacion porque la realidad es que no tenemos suficientes herramientas matematicas como para analizar en profundidad los problemas!

#69 te lo has leido entero y no has entendido nada de nada o has desistido despues del primer paragrafo? Como has preguntado por una explicacion exacta pensaba que tendrias la base necesaria. Si te interesa el tema como para indagar en el te recomiendo empezar por el articulo en ingles de la wiki, luego un par de papers de Avi Widgerson y Mike Sipser:
http://en.wikipedia.org/wiki/P_versus_NP_problem#Notable_attempts_at_proof
http://www.math.ias.edu/_{avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf}
http://www.eecs.berkeley.edu/_{luca/cs172-04/sipser92history.pdf}

Voy a intentar simplificar, pero ahora ya no es lo que significa exactamente sino una aproximacion, y las sutilezas se pierden:

• P y NP son tipos de problemas. Queremos algoritmos que a partir de unos datos de entrada (sean los que sean), encuentren una solucion al problema. Por ejemplo somos unos ladrones y tenemos un conjunto de cosas, cada una con un valor, pero no todas caben en la mochila que llevamos encima. Que cosas metemos en la mochila para que el valor total de lo que nos llevamos sea lo maximo posible? Queremos tener un algoritmo (una serie de instrucciones) que nos diga la mejor manera de llenar nuestra mochila cuando nosotros tengamos una lista de cosas y sus valores. Para no liarnos con optimizacion, queremos ser capaces de responder a la pregunta "Podemos llenar la mochila con objetos con un valor total mayor a 400$?"

• La manera mas obvia de resolver un problema es probar absolutamente todas las soluciones. Asi, un algoritmo para el problema de antes es: Pon todas las cosas que puedas poner en la mochila y apunta el valor. Haz otra combinacion de cosas y vuelve a apuntar el valor. Asi hasta que encuentres una combinacion cuyo valor supere 400$, o las hayas probado todas y ninguna lo supere.

• El problema de este tipo de solucion (fuerza bruta) es que si en lugar de 8 cosas tienes 9, el numero de pruebas que tienes que hacer crece muchisimo, hasta el punto de que con 200 cosas quizas no tengas tiempo suficiente en la historia del universo para probarlas todas. Asi que quieres encontrar* estrategias mas eficientes, mas rapidas, que no crezcan tan rapido con el numero de cosas.

• Los problemas para los cuales hemos encontrado estas instrucciones mas simples que hacen como un "atajo" respecto a probar todo son los que llamamos P. Un ejemplo de problema de este tipo es saber si un numero es primo o no (esto se descubrio en 2002). La manera "bruta" de saberlo es probar a dividir por todos los numeros menores, pero hay una manera mas refinada que resuelve mas rapido.

• Hay problemas para los que no sabemos encontrar una manera simple de resolverlos, pero si que podemos comprobar rapidamente si una solucion es correcta. Por ejemplo si yo te digo "prueba a meter estas cosas en la mochila" tu rapidamente me puedes decir si su valor supera los 400$ o no. Este tipo de problemas son los NP (completo).

• La pregunta es: Hay alguna manera de resolver rapidamente estos problemas que podemos comprobar? Si existiera entonces tendriamos NP=P y muchos ingenieros logisticos/arquitectos de computadores contentisimos.

up

#83 depende de lo que vayas a hacer. Si quieres meterte en comunicaciones opticas por ejemplo, tienes procesos estocasticos y tienes que saber lo que es una sigmaalgebra adaptada, una filtracion del proceso, etc. para entender bien lo que haces. Si haces codificacion de video o teoria de codigos cada vez mas tambien, porque se usan tecnicas muy avanzadas para acercarse a los limites teoricos de compresion... Pero si te llaman otras cosas como antenas y tal pues no hace tanta falta.