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. =)

¿P=NP? La encuesta

Una de las preguntas más famosas relacionadas con la Teoría de la Computación que aún no tienen respuesta es el famoso ¿P=NP? P es una clase de complejidad que representa a los problemas para los cuales se conocen algoritmos que pueden resolverlos en tiempo polinomial determinista. NP es una clase de complejidad que representa a los problemas para los cuales se conocen algoritmos que pueden resolverlos en tiempo polinomial no-determinista, pero no se conocen algoritmos que puedan resolverlos en tiempo polinomial determinista (p.e. Agente Viajero, Satisfacibilidad, The Hamiltonian Path Problem).

Es un problema muy importante para el mundo de la computación. Imagínense, pasándolo a términos prácticos, si descubrimos que P=NP habría una manera de poder resolver cualquier problema computable en tiempo polinomial determinista, i.e. en tiempos humanamente tratables.
Encontré una encuesta que se realizó en el 2002 donde se le preguntaron a varios expertos del área de distintas universidades sobre el problema ¿P=NP? He aquí unos resultados:

¿Cuándo crees que se resuelva P=NP?

1. Entre 2002-2009: 5
2. Entre 2010-2019: 12
   
3. Entre 2020-2029: 13
   
4. Entre 2030-2039: 10
   
5. Entre 2040-2049: 5
6. Entre 2050-2059: 12
   
7. Entre 2060-2069: 4
   
8. Entre 2200-3000: 5
9. Nunca se resolverá: 5

¿Cuál será la respuesta?

1. P = NP : 9
2. P != NP : 61

¿Qué técnicas se usarán en la demostración?

1. Técnicas combinatorias y de complejidad: 11
   
2. Lógica: 9
3. Matemáticas: 10
4. Nuevas técnicas: 16

Hay muchos datos más en la encuesta, por ejemplo algunos investigadores comentan sobre que la solución la dará su universidad, en tal año y usará tal cosa para demostrarla.
El área de complejidad computacional es un mundo lleno de temas divertidos e interesantes. Considero yo que es una de las áreas más importantes en las Ciencias de la Computación.
Yo en particular creo que P != NP, y tú ¿qué piensas? ¿P = NP?

Actualización: No sabía pero me dijo un amigo que en un capítulo de los simpsons está puesta la igualdad, P=NP en el capítulo donde Homero viaja a la tercera dimensión