Computational Complexity

Semester:
7ο
Course Type:
Elective Specialization courses (ΠΜ-E)
Track:
CS (Computer Science), CΕT (Computer Engineering and Telecoms)
Code:
ΘΠ20
ECTS:
6
TEACHING HOURS per week
Theory:
3
Seminar:
1
Laboratory:
-
Specializations
Foundations of Computer Science (Ε1):
-
Data and Knowledge Management (Ε2):
-
Software (Ε3):
-
Hardware and Architecture (Ε4):
-
Communications and Networking (Ε5):
-
Signal and Information Processing (Ε6):
-
Related Courses
Course Content

Turing Machines(Τ.M.) (T.Μ. with multiple tapes, Non-Deterministic Τ.M.). Church-Turing Thesis. Difference in Complexity of T.M., T.Μ. with multiple tapes and Non-Deterministic Τ.M.. Time Complexity of Non-Deterministic T.M.. The class P. The class NP. Syntactic Definition of NP. The class CO-NP. The class EXP. Reductions and Completeness, the notion of NP-Completeness. Cook-Levin Theorem. NP-Complete Languages. Pseudo-Polynomial Algorithms and Strongly NP-Complete Languages. Savitch Theorem. The class PSPACE. PSPACE-Completeness. The classes L, NL and EXPSPACE. NL-Completeness. Space Hierarchy Theorem. Time Hierarchy Theorem.

LITERATURE AND STUDY MATERIALS - READING LIST
  • Michael Sipser, Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης 2007
  • Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική 2005
  • Christos H. Papadimitriou: Computational Complexity, Pearson publications 1993
  • Michael R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company 1979
  • Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press 2007
  • John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley 1979