Computations and Complexity — lectures

7-Dec-2009

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.

30-Nov-2009

PSPACE completeness of
Generalized HEX and EQUIVALENCE of REGULAR EXPRESSIONS.
PSPACE completeness of s-t-CONNECTIVITY for directed graphs represented
by Boolean circuits.

23-Nov-2009

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.

23-Nov-2009

Search problems, optimizaion problems, counting
problems. #P and #P completeness.

Polynomial Hierarchy.
Sigma_i complete problems.

16-Nov-2009

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.

9-Nov-2009

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.

2-Nov-2009

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.

26-Oct-2009

No classes.

19-Oct-2009

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.

12-Oct-2009

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.

5-Oct-2009

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.

28-Sep-2009

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.

21-Sep-2009

No classes.

14-Sep-2009

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.

7-Sep-2009

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