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
2020/2021
Programme:
Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
R1
ECTS:
6
Language:
slovenian, english
Course director:
Prof. Dr. Sergio Cabello Justo, Prof. Dr. Marko Petkovšek
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Content (Syllabus outline)
Readings
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.
Objectives and competences
Students become acquainted with the basic models of computation, the theory of NP-completeness, probabilistic algorithms, and with solving hard problems approximately.
Intended learning outcomes
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.
Learning and teaching methods
Lectures, seminar, exercises, homework, consultations and independent work by the students
Assessment
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)
Lecturer's references
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]
