viernes, 29 de mayo de 2009

Cositas interesantes sobre complejidad

Haciendo tarea de Complejidad Computacional, en un problema nos preguntaban sobre relaciones entre clases de complejidad. Hay clases que no sabía que existían, y fue mi sorpresa ver algunas relaciones padrísimas entre ellas.
Tenemos a viejos conocidos como P y NP. Pero existen otros que suenan un poco raros que, son los que me parecieron interesantísimos.
ZPP: En pocas palabras, esta clase de complejidad, representa a problemas que son resueltos con algoritmos que usan aleatoriedad, y además los resuelven con un 0% de probabilidad de error, terminando en tiempo polinomial.
BPP: Clase de complejidad que representa a problemas que son resueltos con algoritmos que usan aleatoriedad, y además los resuelven con un 1/3 de probabilidad de error, terminando en tiempo polinomial.
RP: Clase de complejidad que representa a problemas que son resueltos con algoritmos que usan aleatoriedad, y además los resuelven con un 1/2 de probabilidad de error, terminando en tiempo polinomial.
Pero ¿qué tiene de interesante esto? ¿Les suenan conocidos los algoritmos evolutivos/genéticos? ¿Heurísticas? Pues sí, ahora lo sabemos, estos algoritmos tienen sus propias clases de complejidad. Leyendo por allí me encontré que existe otro mundo de complejidad que se llama Complejidad Probabilística donde se estudian los algoritmos que involucran al azar y otros aspectos aleatorios.
¿Qué otra cosa importante hay que destacar? Observemos que NP no está contenido completamente en estas clases BPP, ZPP, RP. ¿qué nos dice esto? Esto quiere decir que, existen problemas NP que ni con un algoritmo que use azar (llámese genético, heurístico, evolutivo) se pueden resolver con una probabilidad alta de éxito.
Encontré un wiki en la Universidad de Standford donde está todo el zoológico de clases de complejidad que hay. Una clase al menos para cada letra del alfabeto. =)

5 comentarios:

Oscar Islas L. dijo...

oye y en tus palabras qué sabes del número Omega? ... yo ya lo olvidé ... pero si recuerdo que tiene que ver con probabilidades y así lo bautizó Chaitín ... (una vez Pizaña me dijo que Chaitín era muy creido o egocentrista)

Memo dijo...

Omega(f(n)) indica cotas inferiores.
En lo que refiere a complejidad de tiempo, osea, el número de pasos que tarda en ejecutarse un algoritmo (si tomamos a cada operación como una unidad de tiempo), significa ¿cuántas operaciones se necesitan como mínimo para que un problema tal sea resuelto?

Por ejemplo, en la ordenación de una lista de 'n' elementos. Está demostrado que el mínimo número operaciones que se necesitan para ordenar una lista son n*log(n) operaciones, si es que estás ordenando por comparaciones. Es decir, no existe un algoritmo que use menos de n*log(n) operaciones que ordene una lista de tamaño 'n'. (si es un algoritmo que compara elementos como operación).

La cota inferior de ordenación es OMEGA(n*log(n))

Oscar Islas L. dijo...

no, ese es el orden, el "número omega" es otra cosa, busca chaitín y omega y verás :) suena interesante aunque hay gente que no le cree

Memo dijo...

Wow, no sabía de ese número, está super interesante lo leí de éste documento.
Pues de primera impresión te puedo decir que está de miedo. Valdría la pena escribir una nota referente Oscarín. Me recordó a la película PI el orden del Caos, donde al parecer de PI podías determinar todo lo que ocurría en todos lados, recuerdo que perseguían al protagonista por que tenía las respuestas. También recuerdo que él sabía como la bolsa de valores se iba a comportar en cualquier momentos, entre otras cosas.
Pues si ese número existe, podría controlar el azar, está super rudo, imagínate.

Etna dijo...

Muy lindo :)