[lynal]

Based on a quick skim, this is not a good paper. Computer scientists writing on economics is great, it's helpful to grow new ideas in the field. Unfortunately they sometimes use economic concepts imprecisely at detriment to their question, methodology, and results.

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."

[openasocket]

> 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

[myWindoonn]

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