Re:Markets are efficient if and only if P = NP (2010)
by openasocket on Friday June 01, 2018 @10:51AM
(#17205773)
> Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement?
It actually does have a formal meaning! This is one of the most interesting results (in my opinion) on the P vs NP problem. Given a random oracle R, Pr(P^R != NP^R) = 1. So given a random universe, it is almost certainly true that your version of P != your version of NP. At least that's how my theory prof liked to explain it.
Here's a link with the proof: http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf
Re:Markets are efficient if and only if P = NP (2010)
by myWindoonn on Friday June 01, 2018 @10:15AM
(#17205480)
Whether P and NP are equal is an arithmetic statement; it's either true or not true, but we may not have the proof systems required to demonstrate it.
Your excerpted sentence is already quite concise compared to serious surveys like https://www.scottaaronson.com/papers/pnp.pdf
That's the case here. This paper posits a definition of efficiency, but does not explain why that definition is correct or how it relates to other efficiency measures.
A better proof of arbitrage opportunities in markets is Wah 2016, which identifies actual arbitrage opportunities in actual markets.
Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement?
And what is the correct way to concisely and precisely write: "most people familiar with the P = NP problem believe with varying degrees of confidence that P is not equal to NP, but so far no proof exists."