1. komponenta

Lecture type	Total
Lectures	45

* Load is given in academic hour (1 academic hour = 45 minutes)

COURSE AIMS AND OBJECTIVES: Enable students to:
- Understand how time and space requirements make a concrete problem difficult to solve
- Use reductions to show computational complexity of a given problem

COURSE DESCRIPTION AND SYLLABUS:
1. Complexity. Problems and algorithms. Time and space. Nondeterminism, complexity classes, reductions, completeness.
2. Basic connections. LOGSPACE, P, NP, PSPACE, EXPTIME and NEXPTIME; Cook-Levin theorem.
3. Sample problems. Sorting, 2CNF, 3CNF, SAT, HORNSAT, k-colorability, CLIQUE, Hamiltonian paths, knapsack, travelling salesman, integer linear programming.
4. Savitch's theorem. PSPACE=NPSPACE; PSPACE-completeness, QBF problem, Stockmeyer's theorem.
5. Polynomial hierarchy and circuit complexity. PH and circuits as a model of computation. Karp-Lipton theorem.
6. Probabilistic complexity classes. Probabilistic Turing machines, class BPP. Error reduction and Adleman's theorem.

1. Introduction to the Theory of Computation, 3rd ed., M. Sipser, Cengage Learning, 2013.
2. Computational Complexity: A Modern Approach, S. Arora, B. Barak, Cambridge University Press, 2009.
3. Computational Complexity, C.H. Papadimitrou, Addison Wesley Long., 1994.

Enrollment :
Passed : Mathematical logic

Ostali izborni predmeti - Regular study - Computer Science and Mathematics
Vezani kolegiji A - Regular study - Computer Science and Mathematics

Ostali izborni predmeti - Regular study - Computer Science and Mathematics
Vezani kolegiji A - Regular study - Computer Science and Mathematics

Izborni modul B - Teorijsko računarstvo, 2. godina - Regular study - Computer Science and Mathematics
Ostali izborni predmeti - Regular study - Computer Science and Mathematics
Vezani kolegiji A - Regular study - Computer Science and Mathematics

Izborni modul B - Teorijsko računarstvo, 2. godina - Regular study - Computer Science and Mathematics
Ostali izborni predmeti - Regular study - Computer Science and Mathematics
Vezani kolegiji A - Regular study - Computer Science and Mathematics