Aug 19, 2017

Here's a much more recent and more detailed write up by Scott Aaronson:

Aug 16, 2017

I used to think this, too, but Aaronson changed my mind with the observation in [0] that, if P != NP is independent, then it would necessarily imply a lot of what we would demand from a constructive P = NP proof. In particular, we could get some pretty hilarious improvements on those exponents in NP-complete algorithms, to the point where they become tractable for day-to-day computing.

There is a sense in which any complexity class which is self-low is "physical", or analogous to machines which we might build by hand with modular designs. A self-low class doesn't gain any additional power when relativized with itself as an oracle, and this directly corresponds to building a physical machine out of smaller machine modules.

We know that P is self-low. It seems that the universe insists that either we are able to build machines which tractably solve NP-complete problems, or not, but there is no in-between position.

[0] p28

Aug 14, 2017

Scott Aaronson has done some really good write-ups about P-NP, including what it means and what avenues of proof are possible. I'd start here: It probably doesn't count as "ELI5", but it's something.

Mar 19, 2017

A recent link from Scott Aaronson's blog points to his survey paper on P and NP (

If you think that this brings no "interesting thoughts", this probably says more about your intellectual tastes than it does about Aaronson's work.

Feb 23, 2017

I hugely enjoyed a survey article by Scott Aaronson on P ≟ NP. Section 3.1 contains a discussion on the possibility of the question being independent from ZFC. (He doesn't believe this possibility to be likely.)