Another science fiction story where P=NP by Charles Stross: http://www.antipope.org/charlie/blog-static/fiction/toast/to...

(Put up by the author, so this is not piracy.)

I was a bit taken aback to read that P/NP equality would imply we could compute: "What is the shortest program that in a small amount of time will output the complete works of Shakespeare." since I thought it was proven that determining that some program was the shortest program with a specific output is in general non-computable (relative to some set of axioms, only a finite number of programs are provably the shortest ones producing their outputs.)

Maybe the catch here is the "in a small amount of time"? Or maybe I misunderstood something about Chaitin's "elegant program" idea (where the elegant program for some string S is the shortest one producting S as output.[1])?

I'd be interested in any resolution of this, since it seems unlikely Mr Aaronson would be making a mistake on this topic!

[1] http://www.academia.edu/5838116/Is_incompleteness_a_serious_...

The term is "time-bound kolmogorov complexity". https://en.wikipedia.org/wiki/Kolmogorov_complexity

It's a reference to time-bound solomonoff induction: http://www.scholarpedia.org/article/Algorithmic_probability

edit: also see http://math.uni-heidelberg.de/logic/merkle/ps/mfcs-2009.pdf

Thanks (and other repliers) for the links. I've some reading to do..

Perhaps it's the Bounded Halting Problem which is known to be NPC: http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf

Email him. In my experience he's fantastic about answering questions via email.

Then post his reply here, I'm curious too.

This is a relevant lecture of his which goes into more depth about how to teach QM as a probability theory over complex variables: http://www.scottaaronson.com/democritus/lec9.html

When I read this, I thought it made so much sense.

another great interview! I really enjoy all of nautil.us articles and am very happy Scott did one. I of course recommend all of Scotts essays, including "Why philosophers should care about computational complexity theory" [1] that was submitted to HN recently with some great discussion.

Also, I highly recommend another one of their ingengious series: David Deutsch [2]

[1]: https://news.ycombinator.com/item?id=9061744 [2]: http://nautil.us/issue/2/uncertainty/ingenious-david-deutsch

I've got so much respect for Nautilus for their choice of content, they seem to make things that might seem hard quite approachable without dumbing it down.

Off-topic: Their choice of navigation design for this multi-video interview was horrible. I don't know if there's some esoteric knowledge I lack that would have made the navigation more usable, but this is what I ended up doing: http://i.imgur.com/e4nWbzZ.gif

One of my favorite writers and thinkers. Thanks for posting this.