Semester:
7th
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 (S1):
B Βασικό
Data and Knowledge Management (S2):
-
Software (S3):
-
Hardware and Architecture (S4):
-
Communications and Networking (S5):
-
Signal and Information Processing (S6):
-
Related Courses
Detailed Description
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
e-Class link