This course will begin by explaining the different models of computation. It will then address the Church-Turing thesis. The course will also cover the topics of decidability and reducibility. Finally, detailed information is provided about complexity and related concepts.

Course Objectives

To define and teach different formal models of computation. To give the ability to prove the statements regarding the formal computational models. By covering the complexity classes, to make students use the concepts of NP-completeness to provide proofs for the newly introduced problems.

Recommended or Required Reading

L. Harry R., P. Christos H.,‘Elements of the Theory of Computation’, 2nd Ed., Upper Saddle River, NJ: Prentice-Hall, 1998 ,C. Daniel I.A.,’Introduction to Computer Theory’, 2nd Ed., John Wiley & Sons, Inc., 1997 ,L. Peter, ‘An Introduction to Formal Languages and Automata’,4th Ed., Jones and Bartlett Publishers, Inc., 2001 ,R. Elaine,’Automata, Computability, and Complexity Theory and Applications’, Upper Saddle River, NJ: Prentice-Hall, 2008 ,S. Arora and B. Barak, ’Complexity Theory: A Modern Approach’, Cambridge University Press, Cambridge, 2009 ,S. Cook, ‘The complexity of theorem-proving procedures’, In Proceedings of the 3rd ACM Symposium on the Theory of Computing, ACM, NY, pp 151–158, 1971. ,L. Fortnow, ‘The status of the P versus NP problem’, Commun. ACM. 52, 9 pp 78-86, 2009. ,M. Garey and D. Johnson, ‘Computers and Intractability. A Guide to the Theory of NP-Completeness’ , W. H. Freeman and Company, NY, 1979 ,A. Razborov and S. Rudich, ‘Natural proofs’, Journal of Computer and System Sciences 55, 1 pp 24–35, 1997 ,M. Sipser, ‘Introduction to the Theory of Computation’, PWS Pub. Co, 2005

Learning Outcomes

1. Recognize different computational models

2. Prove the representative models of computation for the given language definitions

3. Distinguish different complexity classes

4. Identify some hard problems of computer science and provide proofs for them

Grading

Midterm Exam: 30%

Homework: 30%

Final Exam: 40%