[yummyfajitas]

I suspect you believe markets are close to efficient. If you don't, you are either investing large fractions of your wealth in a strategy that you believe will beat the market, or you are irrationally throwing your money away. Which is it?

The NP completeness of efficient markets has been known for quite a while.

http://dpennock.com/papers/pennock-ijcai-workshop-2001-np-ma...

It wasn't so long ago that some jerks at Princeton wrote a paper along the same lines, completely ignored all the existing literature to make their paper appear more novel, and got a lot of publicity for themselves (hint: prediction markets are unsexy, CDO's are sexy).

[llimllib]

NP completeness is a strawman here. It's perfectly plausible to have an efficient market where the problem of accurate pricing is NP complete.

Furthermore, the paper you reference (while an excellent and fascinating paper) does not directly bear on the NP completeness of the stock market:

> In Section 3, I discuss the prospect of opening securities markets that pay off contingent on the discovery of solutions to particular instances of an NP-complete problems. Such NP markets would provide direct monetary incentives for developers to test and improve their algorithms, and allow funding agents to target rewards to the designers of the best algorithms for the most interesting problems. In Sections 4 and 5, I discuss markets in #P-complete problems, where prices serve as collective approximate bounds on the number of solutions, and bid-ask spreads may indicate problem difficulty

is his summary of what the paper does (sections 1 and 2 are introductory material). I claim that this does not at all show the NP completeness of markets, and further that it's a claim irrelevant to the discussion here.

In what sense are you claiming that he proves the "NP completeness of markets"? What does that mean? Why is it relevant to whether or not to invest money in the stock market?

(sidenote: I don't think the question of the NP-completeness of some questions related to stock pricing is irrelevant or uninteresting; indeed I just applied to grad school to study problems like these. I just don't think they bear on what you're implying they do)

That said, I voted you up because of your first sentence.

[yummyfajitas]

Neither the paper I linked to nor the paper written buy the Princeton guys shows that equities markets are NP complete. They both show that markets in certain derivatives are NP complete.

However, I made a mistake and linked to the wrong paper. Here is the correct one:

http://dpennock.com/papers/fortnow-dss-2004-compound-markets...

Basically, the result says that if you have a market in derivatives which pays off when certain formulas in propositional logic are true (e.g., a derivative which pays off if A && (!B || C) is true, for specific events A,B,C), then the auctioneer's matching problem is NP complete. The auctioneer's matching problem is simply market making, and if the market were efficient, this problem would already be solved (by looking at prices).

I don't think that loewenskind's claim is true, for the most part, I was just providing a more detailed source on NP completeness of some markets.

[contextfree]

Hypothetically, couldn't I believe that some large inefficiency exists but that I don't know what it is?