3 ms·
Scott Aaronson, from computational complexity to quantum mechanics
- diego898 12y agoanother 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 https://news.ycombinator.com/item?id=9061744 [2]: http://nautil.us/issue/2/uncertainty/ingenious-david-deutsch http://nautil.us/issue/2/uncertainty/ingenious-david-deutsch
- jerf 12y agoAnother science fiction story where P=NP by Charles Stross: http://www.antipope.org/charlie/blog-static/fiction/toast/toast.html#antibodies http://www.antipope.org/charlie/blog-static/fiction/toast/to... (Put up by the author, so this is not piracy.)
- davesque 12y agoOne of my favorite writers and thinkers. Thanks for posting this.
- vecter 12y agoThis 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 http://www.scottaaronson.com/democritus/lec9.html When I read this, I thought it made so much sense.
- ttctciyf 12y agoI 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_problem http://www.academia.edu/5838116/Is_incompleteness_a_serious_...
- BrainInAJar 12y agoEmail him. In my experience he's fantastic about answering questions via email. Then post his reply here, I'm curious too.
- rndn 12y agoPerhaps it's the Bounded Halting Problem which is known to be NPC: http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf
- deleted 12y ago[deleted]
- emmab 12y agoThe term is "time-bound kolmogorov complexity". https://en.wikipedia.org/wiki/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 http://www.scholarpedia.org/article/Algorithmic_probability edit: also see http://math.uni-heidelberg.de/logic/merkle/ps/mfcs-2009.pdf http://math.uni-heidelberg.de/logic/merkle/ps/mfcs-2009.pdf
- ttctciyf 12y agoThanks (and other repliers) for the links. I've some reading to do..
- arvinjoar 12y agoI'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 http://i.imgur.com/e4nWbzZ.gif