TEDxCaltech - Scott Aaronson - Physics in the 21st Century: Toiling in Feynman's Shadow
Why Theoretical Computer Science Stack Exchange recommends it
Theoretical Computer Science Stack Exchange users link it as an accessible, funny introduction to P vs NP and quantum computing, and as a go-to video for explaining complexity ideas to non-experts.
Recommended by 3 people across 3 different months, 2011 to 2012.
What it is
A 15-minute TEDxCaltech talk given by MIT computer scientist Scott Aaronson in honor of Richard Feynman. He covers quantum computing, the limits of what can be efficiently computed in the physical world, and the P vs NP question, in a clear and humorous style for a general audience.
What people said
Recommends Pratik Deoghare · 2011-02 · Theoretical Computer Science Stack Exchange · on “Explain P = NP problem to 10 year old”
In this talk Scott Aaronson [LINK] addresses the question. TEDxCaltech - Scott Aaronson - Physics in the 21st Century: Toiling in Feynman's Shadow [this video] Warning: Please, do NOT show this talk directly to your grandmother/ 10 year old. why? watch it and you will know. ;-) EDIT: Give the kid 8 queens puzzle [LINK] to solve. Also give him time limit. If he "finds" a solution then he is one smart kid you can start teaching him CS right away. :) Else you show him the solution and ask him to "check" if its correct. $$\begin{array}{|l|l|l|l|} Class & Check & Find & Example \\ \hline \mathsf{P} & Easy & Easy & Multiply \ numbers \\ \mathsf{NP} & Easy & Hard & 8 \ queens \end{array}$$ $\mathsf{P}$
Recommends Huck Bennett · 2011-02 · Theoretical Computer Science Stack Exchange · on “What videos should everybody watch?”
I enjoyed Scott Aaronson's lecture at Caltech [this video] titled "Quantum Computing and the Limits of the Efficiently Computable." This lecture, which was in honor of Feynman, rehashes what's common knowledge to users of this site but in a very clear and funny way.
Recommends Pratik Deoghare · 2011-08 · Theoretical Computer Science Stack Exchange · on “Long-lasting errors in computer science”
Watch this TED talk [this video] . But thinking that something is obvious doesn't prove anything and is of no use.
Recommends Marzio De Biasi · 2012-03 · Theoretical Computer Science Stack Exchange · on “Proofs on unconventional computing”
I suggest you this survey/introduction paper (but perhaps you alredy read it): Unconventional computing: a short introduction [LINK] by M. Oltean (2009). It is a little bit funny (see for example the "Price" column in the comparison table) ... however the references at the bottom can lead you to other relevant papers. I'm not an expert but searching papers on other subjects I sometimes found titles about the "DNA computing" model , so - if you classify Quantum Computing conventional computing :-) - I think it is one of the most studied model, and there are many results out there (see for example " A Robust DNA Computation Model that Captures PSPACE [LINK] "). I'm curious to see other answers
Cites codd · 2011-06 · Theoretical Computer Science Stack Exchange · on “Are quantum computers turing complete?”
I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial time just amazes me. The only real knowledge I have about the model is stuff I picked up from the blog and from recent [this video] video's where Aaronson discusses the subject. I have also recently read [LINK] that the first quantum computer was sold. Now I am wondering, and I hope this is not a stupid question, is quantum computing a turing complete computational model? Also, how come there is an efficient factoring algorithm and not, say, an efficient algorithm for the graph isomorphism problem? W