COURSE AIMS AND OBJECTIVES: The complexity classes are studied. Examples of different problem will explain and describe some classes. Some open problems of complexity theory are emphasized. At the end descriptive complexity theory are considered.
COURSE DESCRIPTION AND SYLLABUS:
- Complexity: problems and algorithms; time and space, non-deterministic computation, complexity classes, reductions, completeness.
- Basic relations: LOGSPACE, P, NP, PSPACE, EXPTIME i NEXPTIME; Cook - Levin theorem.
- Examples of problems: sorting, 2CNF, 3CNF, SAT, HORNSAT, graph coloring, CLIQUE, Hamiltonian path problem, knapsack problem, minimum travelling salesperson problem.
- Savitch theorem: PSPACE=NPSPACE; PSPACE-completeness, QBF problem, Stockmeyer's theorem.
- Probabilistic algorithms: probabilistic Turing machine; class BPP; examples of problem.
-Cryptography: private and public keys; one way functions.
- Descriptive complexity theory: fixed point logics, expressive power, Fagin's theorem.
|
Pristupačnost
