Models of computation. Time and space complexity. Determinism and nondeterminism. Reductions and completeness.

NP-completeness. Some selected NP-complete problems. Techniques to prove NP-completeness. Structure of the class NP.

Probabilistic algorithms. Types of probabilistic algorithms. Related computational classes. Pseudorandom generators.

Approximation algorithms. Quality of approximation. Hardness of approximation. Approximation schemes. Selected approximation algorithms.

Additional content may be selected among the following topics: Boolean circuits, interactive proofs, quantum computing, PCP theorems, communication complexity, parameterized complexity.

# Computational complexity

Prof. Dr. Sergio Cabello Justo, Prof. Dr. Marko Petkovšek

S. Arora, B. Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

M. R. Garey, D. S. Johnson: Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman and Co., 2003.

R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, Cambridge, 1995.

V. V. Vazirani: Approximation algorithms, Springer-Verlag, 2001.

Students become acquainted with the basic models of computation, the theory of NP-completeness, probabilistic algorithms, and with solving hard problems approximately.

Knowledge and understanding: The students understand:

connections between models of computation,

theory of NP-completeness,

the concept of probabilistic algorithm,

the concept of approximation algorithm.

Application: The students are able to:

analyze time complexity of algorithms,

prove NP-completeness,

design probabilistic algorithms,

design approximation algorithms.

Reflection: The students meet:

problem hierarchies by time complexity,

inherently hard problems,

relaxations to solve hard problems.

Transferable skills: Analysis of the hardness of problems using reductions between them.

Lectures, seminar, exercises, homework, consultations and independent work by the students

Exam of exercises (2 midterm exams or written exam) or homework

Oral exam

grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Sergio Cabello:

CABELLO, Sergio, CARDINAL, Jean, LANGERMAN, Stefan. The clique problem in ray intersection graphs. Discrete & computational geometry, ISSN 0179-5376, 2013, vol. 50, iss. 3, str. 771-783. [COBISS-SI-ID 16728921]

CABELLO, Sergio. Hardness of approximation for crossing number. Discrete & computational geometry, ISSN 0179-5376, 2013, vol. 49, iss. 2, str. 348-358. [COBISS-SI-ID 16340313]

CABELLO, Sergio, LUKŠIČ, Primož. The complexity of obtaining a distance-balanced graph. The Electronic journal of combinatorics, ISSN 1077-8926. [Online ed.], 2011, vol. 18, no. 1, p49 (10 str.). [COBISS-SI-ID 15832153]

Marko Petkovšek:

PETKOVŠEK, Marko, PISANSKI, Tomaž. Izbrana poglavja iz računalništva. Del 1, Izračunljivost in rešljivost, jeziki, NP-polnost, naloge, (Matematični rokopisi, 1.a.). 1986: Društvo matematikov, fizikov in astronomov SRS, Ljubljana. 120 str. [COBISS-SI-ID 519702]

PETKOVŠEK, Marko, WILF, Herbert S., ZEILBERGER, Doron. A=B. Wellesley (Massachusetts): A. K. Peters, cop. 1996. VII, 212 str. ISBN 1-56881-063-6. [COBISS-SI-ID 4085337]

PETKOVŠEK, Marko. Letter graphs and well-quasi-order by induced subgraphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2002, vol. 244, no. 1-3, str. 375-388. [COBISS-SI-ID 11414873]