Certification Programme description: Introduction to computational complexity theory; Calculation model based on Turing machine: formal definition, representation and language of Turing machine, recursive and recursively enumerable languages, Program definition and machine's state representation, machine's resource requirements, multi-track Turing machine, Non-deterministic Turing machine; Alternate models of complexity: RAM machine, instruction set, language recognition by RAM machine, Computational complexity in RAM model, comparison of time usage of RAM and Turing machines, Simulating the RAM machine by multi-track Turing machine, Comparison of memory complexity between computational models, Logical circuits; Computational complexity classes: Time and memory complexity classes, Linear acceleration and memory compression theories, Relations between classes, Savitch's theorem, class complements, Time and memory hierarchy theories; Reductions, Completeness and NP-complete problems: Polynomial and logarithmical reductions, polynomial transformation by Turing, NP class and NP-completeness (NP class in language of logic, existential 2-nd class statements and complexity, Fagin theorem), SAT, 3SAT, MAXSAT problems, NP-complete graph problems, Node cover, Clique, Independent set, Problems over sets and numbers (tripartite matching and set cover, subset sum and other numerical problems); Algorithms and approximation schemes: optimization and decision problems, Approximation solutions, greedy algorithms, MAX CUT problem, TSP problem, metric version, BIN PACKING, 2-approximation, KNAPSACK problem, Approximation schemes, L-reductions; Probabilistic algorithms: probabilistic complexity classes (ZPP, PP and BPP classes), prime numbers detection, Miller-Rabin test, Random bits generation, Models of concurrent calculations (PRAM), Classes in PRAM models, P-completeness, Concurrency and randomization; Function problems and computational complexity: FP, FNP and TFNP classes, #P class, Valiant theorem, Parity-P class; Logarithmical memory, polynomial hierarchy, polynomial memory and exponential complexity: L, NL and coNL classes, Immerman-Szelepcsényi theorem, coNP and DP classes, Alternating machines, PSPACE class, PSPACE-complete problems (periodical optimization), Regular expressions; Cryptography and complexity: one-way functions
Certification Programme version/revision: EITC/FC/CCTv1r2)Earned ECTS credits: 2
