El modelo clásico de Markowitz es un problema de programación cuadrática. No estoy seguro del estado de la investigación actual, pero un artículo que podría constituir un punto de partida está aquí: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.9504
Por cierto, hay un artículo que ha estado dando vueltas sobre temas relacionados: "Complejidad computacional y asimetría de información en productos financieros" por Sanjeev Arora, Boaz Barak, Markus Brunnermeiery y Rong Ge. Este último lo ha publicado junto con algunos comentarios adicionales aquí: http://www.cs.princeton.edu/~rongge/derivativeFAQ.html
Tiendo a pensar que los resultados son de interés teórico, pero no explican nada de lo que realmente sucedió.
Mi sospecha es que la complejidad no es la barrera principal en la mayoría de los modelos (en general, cualquier cosa complicada se convierte en un monte-carlo eventualmente de todos modos, y en general las cosas se complican rápidamente, así que sí, esto abre el camino a ciertos ataques maliciosos, pero la malicia en el mundo financiero puede ser mucho más fácilmente crudo, general y directo) que muchas otras críticas generalmente conocidas de estos modelos (a veces desde el punto de vista de la teoría de la información) que no son realmente apropiadas para este foro.