Scott Aaronson, from computational complexity to quantum mechanics | Hacker News Reader

Scott Aaronson, from computational complexity to quantum mechanics

nautil.us

58 pointsdnetesn10 comments

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

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

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

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

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

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.

Reply on news.ycombinator.com