Computations and Complexity — lectures
Containment of BPP in P/poly.
Containment of BPP in Sigma2.
Rabin’s algorithm for primality testing.
Randomized algorithms. Class BPP.
Polynomial identity testing.
PSPACE completeness of
Generalized HEX and EQUIVALENCE of REGULAR EXPRESSIONS.
PSPACE completeness of s-t-CONNECTIVITY for directed graphs represented
by Boolean circuits.
Class PSPACE. Containment of PH in PSPACE.
CLass EXPTIME and containment of PSPACE in EXPTIME.
Game characterization of PSPACE. PSPACE complete problems (BQF).
#P completeness of #CNF revisited (a correct proof).
#P completeness of permanent (without proof).
Perfect matching is in P.
Search problems, optimizaion problems, counting
problems. #P and #P completeness.
Sigma_i complete problems.
Polynomial mapping reducibility. NP hard and NP complete problems.
Cook-Levin theorem on NP completeness of CIRCUIT-SAT
NP completness of 3-CNF, CLIQUE, VERTEX COVER, INDEPENDENT SET,
SUBSET SUM, HAMILTONIAN CYCLE, 3-COLORING.
2-CNF and 3-COLORING are in P.
Lower bound 2^n/n.
The containment of P in nuP.
Class P/poly and the equality
Class NP, examples.
Fisher-Rabin theorem (the proof).
Boolean circuits and formulae. Curcuit complexity.
Polynomial upper bound for circuit complexity of
addition and multiplication.
Independence of the basis. Upper bound n2^n.
Class P of polynomial time decidable languages.
Class PF of polynomial time computable functions.
Independency of these classes on the machine models.
Hierarchy theorems. Using hierarchy theorems for proving
lower bounds. Fisher-Rabin theorem.
Undecidability of the word equivalence problem for
rewriting systems (Semi-Thue systems). Undecidability of the
word problem for finitely presented semi-groups (Thue systems).
Time and space of computations for Turing machines. Simulation
of multi-tape Turing machines on 1-tape Turing machines.
Turing machines for arithmetical operations on integers.
Rice-Uspensky theorem revisited, examples of applications.
Why every computable functions has infinitely many numbers
in any Goedel numbering.
Fixed point theorem and recursive programs (computing n factorial).
Mapping reducibility and examples. m-Complete enumerable sets.
All m-complete enumerable sets are isomorphic. Simple sets,
their existence and m-incompleteness.
Turing reducibility. Friedberg-Muchnik theorem.
Turing machines. Church-Turing thesis.
Partial computable function that has no total computable extensions.
Non-existence of universal total computable functions.
A new example of an enumerable decidable set. A new proof of
the undecidability of the halting problem.
Ispeparable enumerable sets.
Computability and enumerability: theorem on the graph of a
Decidability and enumerability: theorem on the projection of a
Goedel numberings of the family of computable partial
Rice-Uspensky theorem. Fixed point theorem.
Finding the heaviest and second heaviest objects in n+log n
Lower bound n+log n for finding
the heaviest and second heaviest objects
Computable total and partial functions from N to N.
Existence of non-computable total functions. Decision
problems and decidable sets. Closure properties of
(Computably) enumerable sets and their closure properties.
Enumerable sets as domains and ranges of partial computable functions.
Undecidability of the halting problem. Universal computable function.
10 questions lower and upper bounds. Non-adaptive algortithms.
Finding the radioactive object using Geiger device.
Finding the heaviest object using a scale: upper and lower bound n-1.
Sorting: lower bound log n!, upper bound \log n!+n
Sorting 5 objects in 7 comparisons.
Finding the heaviest and lightest object in 3n/2
Lower bound 3n/2 for finding the heaviest and lightest object