Scott in Rio — 1st lecture
complexity-theoryquantum-computingbosonsamplingchurch-turingp-vs-np
Abstraction: Scott Aaronson lecture on complexity theory foundations and Extended Church-Turing thesis
Key points:
- Extended Church-Turing (ECT) thesis: all efficiently physically computable functions can be efficiently computed by a Turing machine; "efficient" means polynomial-time p(n) steps in input size n
- Shor's quantum factoring algorithm challenges the ECT since no known efficient classical algorithm for factoring exists, though one might exist undiscovered
- P = languages decidable in polynomial time; NP = languages whose solutions can be verified in polynomial time (non-deterministic polynomial); NP-Hard = any NP problem poly-time reducible to it; NP-Complete = NP ∩ NP-Hard
- Lecture series centers on BosonSampling as a physical implementation potentially violating the ECT
- Scott Aaronson (MIT) delivered the crash course to a mixed audience of physicists, mathematicians, and CS researchers at Infoptics@UFF, Rio
Connections: Scott Aaronson · Computational Complexity · Quantum Computing · Boson Sampling · Church Turing Thesis
Source: http://quantumrio.wordpress.com/2013/12/18/scott-in-rio/