Õppeaine eesmärk on tutvustada keerukusteooria põhitulemusi ning meetodeid praktilises programmeerimistöös tekkivate probleemide keerukuse hindamiseks.

The aim of the course is to introduce the main outcomes and methods of complexity theory in assessing the complexity of problems that arise in practical programming work.

Aine läbinud üliõpilane
* Saab aru keerukusklasside P, NP, coNP, #P ja Polünomiaalse Hierarhia olemusest.
* Saab aru klassikalise keerukusteooria teoreemide tõestustest.
* Oskab hinnata lahendamist vajavate probleemide keerukust.
* Oskab tõestada etteantud probleemi NP-täielikkust.

On completion of the course, the student:
* Understands the nature of complexity classes P, NP, coNP, #P and Polynominal Hierarchy.
* Understands the proving of classical complexity theory theorems.
* Can evaluate the complexity of the problems to be solved.
* Can prove the NP-completeness of a given problem.

Lausearvutuse valemite väärtustamise, kehtestatavuse ja lahendite loendamise ülesanded. Tagurdusalgoritm kehtestatavuse testimiseks. Disjunktiivne ja konjunktiivne normaalkuju (DNF, CNF). Tagurdusalgoritm konjunktiivsele normaalkujule. DPLL halvima juhu eksponentsiaalne keerukus. Lahendite loendamine ellimineerimismeetodil. Ortogonaliseerimine. Ortogonaalne DNF. Moon-Moseri graafid ja loendamisalgoritmide eksponentsiaalsus. Dedekindi arvud. Polünomiaalne taandamine. NP-rasked ja NP-täielikud probleemid. Kehtestatavuse probleem. Klikk, sõltumatu hulk ja tippude kate. Cook-Levini teoreem. Rändkaupmehe ülesanne. Graafi tippude värvimine. Kahe- ja kolmemõõtmeline sobitusülesanne. Keerukusklass coNP. Turingi taandamine. Polünomiaalne hierarhia. Pehouseki teoreem. Interaktiivsed protokollid.

Tasks for the valuation, satisfiability and for counting the solutions of propositional formulae. Backtracking algorithm for testing satisfiability. Disjunctive and conjunctive normal form (DNF, CNF). Backtracking algorithm for conjunctive normal form. DLPP worst case scenario exponential complexity. Counting the solutions through the exclusion-inclusion principle. Orthogonalisation. Orthogonal DNF. Moon-Moser graphs and the exponentiality of counting algorithms. Dedekind numbers. Polynominal reduction. NP-hard and NP-complete problems. The problem of satisfiability. Clique, independent set and vertex cover. Cook-Levin theorem. Travelling salesman problem. Colouring the graph vertices. Two- and three-dimensional matching problem. Complexity class coNP. Turing reduction. Polynominal hierarchy. Pehousek’s theorem. Interactive protocols.

Eksam koosneb teooriast ning ülesannetest arusaamise ja loomingulise mõtlemise kontrolliks.

The examination consists of theory and the exercises for the assessment of understanding and creative thinking.

4*16 tundi loenguid ja 92 tundi iseseisvat tööd. Kokku 156 tundi. 92 tundi iseseisvat tööd sisaldab koduseid ülesandeid ja teooria õppimist eksamiks valmistumisel.

4*16 h of lectures and 92 h of independent work. Total of 156 hours. 92 h of independent work includes homework and examination preparation by studying theory.

Mati Tombak. Keerukusteooria. Tartu, 2007.

-