Poll

No polls currently selected on this page!

Repository

Repository is empty

Algorithm complexity

Code: 92958
ECTS: 5.0
Lecturers in charge: prof. dr. sc. Mladen Vuković - Lectures
English level:

1,0,0

All teaching activities will be held in Croatian. However, foreign students in mixed groups will have the opportunity to attend additional office hours with the lecturer and teaching assistants in English to help master the course materials. Additionally, the lecturer will refer foreign students to the corresponding literature in English, as well as give them the possibility of taking the associated exams in English.
Load:

1. komponenta

Lecture typeTotal
Lectures 45
* Load is given in academic hour (1 academic hour = 45 minutes)
Description:
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.
Literature:
  1. M. Sipser: Introduction to the Theory of Computation
  2. H. D. Ebbinghaus, J. Flumm: Finite model theory
  3. C. H. Papadimitriou: Computational Complexity
Prerequisit for:
Enrollment :
Passed : Computability
Passed : Design and analysis of algorithms
4. semester
Mandatory course - Regular study - Computer Science and Mathematics
Consultations schedule: