Cuando estaba en la escuela, hace algunos años, había gran efervescencia sobre el tema del computo paralelo, de hecho mi tesis doctoral es sobre este tema. Recuerdo que comentado sobre las posibilidades del paralelismo con mi asesor, me dijo que desde un punto de vista teórico el computo paralelo no era importante porque no cambiaba los limites de escalabilidad impuestos por los problemas NP.
Ahora nos encontramos en un resurgimiento de los enfoques del computo distribuido debido al abaratamiento del hardware y la cada vez mayor disponibilidad de conexiones de banda ancha. Por lo tanto la cuestión de algoritmos eficientes para problemas NP y la corroboración teórica de NP ǂ P se ha convertido en uno de los problemas primordiales de la teoría y practica del computo.
Referencias
- Computational Complexity: A Modern Approach
- Complexity: A Guided Tour
- http://www.cs.princeton.edu/theory/complexity/
- http://en.wikipedia.org/wiki/Computational_complexity_theory
- http://delivery.acm.org/10.1145/1570000/1562186/p78-fortnow.pdf?key1=1562186&key2=2877581521&coll=GUIDE&dl=GUIDE&CFID=49818716&CFTOKEN=74286876
- http://blog.computationalcomplexity.org/