Academic Catalog

CENG565 INTRODUCTION TO THEORY OF COMPUTATION

Course Code: 5710565
METU Credit (Theoretical-Laboratory hours/week): 3(3-0)
ECTS Credit: 8.0
Department: Computer Engineering
Language of Instruction: English
Level of Study: Graduate
Course Coordinator: Academic Staff Dr. AYE NUR BRTRK
Offered Semester: Fall or Spring Semesters.

Course Content

Turing machines. Church-Turing thesis. Decidability. Reducibility and Recursion Theorem. Complexity theory: Classes P and NP, NP-Completeness. Space Complexity. Intractability.