Computational complexity

Course objectives

Introducing basic models of computation used in computational complexity (decision trees, multi-tape Turing machines, random access machines, Boolean circuits, probabilistic versions of these models).
Developing skills of analysis of time and space required for a realization of an algorithm in a computational model.
Developing skills of distinguishing different types of computational hardness (worst case hardness and average case hardness).
Learning methods of establishing computational hardness of problems of different kinds (problems of computing a function, search problems, optimization problems, approximation problems, counting problems): proving hardness of model problems and reducing other problems to model ones.

Tentative contents

Basic models of computation: multi-tape Turing machines and random access machines. Upper bounds of time and space sufficient to perform basic arithmetical algorithms over integer numbers.
Polynomial equivalence with respect to time and space of different models of computation. The class P of functions computable in polynomial time.
Reductions between problems. Problems that are complete in a class of problems. The hierarchy theorem as a method of proving computational hardness.
Provably hard algorithmic problems: testing equivalence of extended regular expressions, deciding validity of formulas of the first order logic in the additive group of real numbers.
The class NP of decision problems. Search problems and the class SearchP. Reducing any search problem to a decision problem in the class NP. Counting problems and the class #P.
NP-hard and NP-complete problems. P=NP question and presumable hardness of NP-hard problems.
Boolean circuits. Cook-Levin's theorem of NP-completeness of the circuit satisfiability problem.
NP-completeness of other problems: 3-CNF (3-SAT), 3-Colorability, Clique, Vertex Cover, Hamiltonian Cycle, Knapsack, Traveling Salesman, Integer Linear Programming.
Optimization problems. Reducing every optimization problem to a decision problem in NP. Approximate solutions of optimization problems. NP-hardness of the problem of approximating the chromatic number of a given graph.
#P-completeness of counting problems.
Polynomial time games and the class PSPACE of problems solvable in polynomial space. The inclusion of NP in PSPACE.
Randomized polynomial time algorithms and the class BPP of problems solvable by randomized polynomial time algorithms with a small probability of error. Amplification.
Class nuP of decision problems solvable by Boolean circuits of polynomial size (in the length of input). Inclusion of the classes P and BPP in the class nuP.
PSPACE-complete problems.
Probabilistically checkable proofs and PCP-theorem of existence of probabilistically checkable proofs for every language in NP. Applications of PCP-theorem to proving NP-hardness of approximate solutions of optimization problems.
Average case complexity. Average NP-completeness of the tiling problem.
Non-invertible and one way functions. Pseudo random numbers generators. Using one way permutations to construct pseudo random numbers generators.