Containment of BPP in P/poly. Containment of BPP in Sigma2.
Rabin's algorithm for primality testing.
Randomized algorithms. Class BPP. Amplification. 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.
Polynomial Hierarchy. 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. Class nuP. The containment of P in nuP. Class P/poly and the equality P/poly=nuP.
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.
Church-Turing thesis. 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 computable function. Decidability and enumerability: theorem on the projection of a decidable set.
Goedel numberings of the family of computable partial functions.
Rice-Uspensky theorem. Fixed point theorem.
Finding the heaviest and second heaviest objects in n+log n comparisons.
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 decidable sets. (Computably) enumerable sets and their closure properties. Enumerable sets as domains and ranges of partial computable functions. Post's theorem.
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 comparisons.
Lower bound 3n/2 for finding the heaviest and lightest object