Table of Contents
Church of theMillennium:Reflections on the validity of the Church-Turing thesis, and its refinements, in 1999
Foreword
Outline
Quantum computing
Factoring
Quantum factoring
Why of interest to TCS?
Why of interest to TCS?
Why of interest to TCS?
Why of interest to TCS?
Formalising ‘computation’, 1931
Church-Turing thesis
Computational complexity theory
Where are the tractable problems?
The Invariance Thesis
The Invariance Thesis
The Invariance Thesis
First and second machine classes
Solving intractable problems
P=?NP
Future...
Conclusions
PPT Slide
|
Author: Computer Science Dept.
Email: tomn@cs.may.ie
Home Page: http://www.cs.may.ie/~tnaughton
|