The classic Markowitz model is a quadratic programming problem. I'm not sure at all about the state of current research, but one paper that might constitute a starting point is here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.9504
By the way, there's a paper that's been making the rounds on related issues: "Computational Complexity and Information Asymmetry in Financial Products" by Sanjeev Arora, Boaz Barak, Markus Brunnermeiery, and Rong Ge. The latter has posted it along with some additional comments here: http://www.cs.princeton.edu/~rongge/derivativeFAQ.html
I tend to think the results are of theoretical interest but don't explain anything that actually happened.
My suspicion is that complexity is not the main barrier in most models (generally, anything complicated gets turned into a monte-carlo eventually anyway, and generally things get complicated fast -- so yes this opens the way to certain malicious attacks, but maliciousness in the financial world can much more easily be much more crude, general, and straightforward) so much as many other, generally well known critiques of these models (sometimes from an information theory standpoint) that aren't really appropriate for this forum.