O modelo clássico de Markowitz é um problema de programação quadrática. Não tenho certeza do estado da pesquisa atual, mas um artigo que pode constituir um ponto de partida está aqui: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.9504
A propósito, há um artigo que está circulando sobre questões relacionadas: "Complexidade computacional e assimetria de informação em produtos financeiros", de Sanjeev Arora, Boaz Barak, Markus Brunnermeiery e Rong Ge. Este último publicou-o juntamente com alguns comentários adicionais aqui: http://www.cs.princeton.edu/~rongge/derivativeFAQ.html
Costumo pensar que os resultados são de interesse teórico, mas não explicam nada que realmente aconteceu.
Minha suspeita é que a complexidade não é a principal barreira na maioria dos modelos (geralmente, qualquer coisa complicada acaba se transformando em um monte-carlo de qualquer maneira, e geralmente as coisas ficam complicadas rapidamente - então sim, isso abre caminho para certos ataques maliciosos, mas maliciosos em o mundo financeiro pode muito mais facilmente ser muito mais bruto, geral e direto), assim como muitas outras críticas geralmente conhecidas desses modelos (às vezes do ponto de vista da teoria da informação) que não são realmente apropriadas para este fórum.