Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Introduction to Complexity and Computability - NTIN090

Title:	Základy složitosti a vyčíslitelnosti
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2015 to 2016
Semester:	winter
E-Credits:	5
Hours per week, examination:	winter s.:2/1, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time
Additional information:	http://ktiml.mff.cuni.cz/~kucerap/NTIN090/index.html

Guarantor:	prof. RNDr. Ondřej Čepek, Ph.D. RNDr. Petr Kučera, Ph.D.
Class:	Informatika Mgr. - učitelské studium informatiky Informatika Mgr. - Softwarové systémy Informatika Mgr. - Matematická lingvistika M Mgr. MSTR M Mgr. MSTR > Povinně volitelné
Classification:	Informatics > Theoretical Computer Science
Interchangeability :	{Složitost I a Vyčíslitelnost I}
Incompatibility :	NTIN062, NTIN064
Is interchangeable with:	NTIN062

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: T_KTI (28.04.2015)

This is a basic course on the theory of algorithms, computability and computational complexity. Roughly the first half of the course is devoted to the introduction to computability theory: Turing machines. Computable functions. Recursive and recursively enumerable languages and sets. Undecidable problems. The second half of the course is devoted to the study of space and time complexity classes: Equivalence of PSPACE and NPSPACE. Deterministic hierarchy theorems. Class NP. Polynomial reducibility among problems. Proofs of NP- completeness. Approximation algorithms and approximation schemes.

Aim of the course -

Last update: RNDr. Petr Kučera, Ph.D. (04.09.2014)

To teach basics of complexity theory and theory of computation.

Literature -

Last update: doc. RNDr. Pavel Töpfer, CSc. (25.05.2022)

Lecture web pages (lecture presentation can be found there): http://ktiml.mff.cuni.cz/~kucerap/NTIN090/index-en.html

Sipser, M. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.

Demuth O., Kryl R., Kučera A.: Teorie algoritmů I, II. SPN, 1984, 1989 (Only in Czech)

Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

Odifreddi P.: Classical recursion theory, North-Holland, 1989

Garey, Johnson. Computers and intractability - a guide to the theory of NP-completeness, W.H. Freeman 1978

Arora S., Barak B.: Computational Complexity: A Modern Approach. Cambridge University Press 2009 (Draft available online).

Syllabus -

Last update: doc. RNDr. Pavel Töpfer, CSc. (14.01.2019)

1) Turing machines and their variants, Church-Turing thesis.

2) Halting problem

3) RAM and their equivalence with Turing machines. Algorithmically computable functions.

4) Recursive and recursively enumerable languages and sets and their properties.

5) 1-reducibility and m-reducibility, 1-complete and m-complete sets.

6) Rice's theorem.

7) Nondeterministic Turing machines, basic complexity classes, classes P, NP, PSPACE, EXP.

8) Savitch's theorem - equivalence of PSPACE and NPSPACE.

9) Deterministic space and time hierarchy theorems.

10) Polynomial reducibility among problems. NP-hardness and NP-completeness.

11) Cook-Levin theorem, examples of NP-complete problems, proofs of NP-completeness.

12) Pseudopolynomial algorithms and strong NP-completeness.

13) Approximations of NP-hard optimization problems. Approximation algorithms and schemes.

14) Classes co-NP and #P.