Theory of Computing


  • Instructor: Vince Grolmusz, (

  • 1: Finding a lost lion in the Sahara, binary search. Twenty questions games: finding out a 32-bit number, finding out a 32-bit number with at most one lie. Finding the MAX, the MIN, the MAXMIN. The optimality of the MAXMIN algorithm. Sorting with pairwise comparisons needs log (n!) steps.

    2: Estimations of log (n!), Sorting, insertion-sort with $O(n\log n)$ comparisons, merging two sorted sequences of length n with 2n-1 comparisons, this is optimal. Merge sort. On average, also $\Omega(n\log n)$ comparisons are needed to sort n numbers.

    3: Communication Complexity: The Encylopaedia Britannica problem, communication matrix, the logarithm of the rank of the communication matrix is a lower bound to the communication complexity. Subtree-intersection protocol. The set-disjointness problem. The E.T. comes: non-deterministic communication complexity. Characterization of the non-deterministic communication complexity with covering rectangles.

    4: Randomized protocol for the Encylopaedia Britannica problem (Rabin and Simon). Applications of the communication complexity in VLSI design: a time-area trade--of: Thompson's theorem.

    5: k-tape Turing machines, examples. Universal Turing machines. Recursive, recursively enumerable languages. The halting problem.

    6: Detrministic time- and space complexity classes. Definition of P. Examples: Euclidean algorithm, computing a^b mod m. Non-deterministic Turing-machines. The definition of NP.


    Witness, defining NP with polynomial witnesses. Primes $\in$ coNP. Pratt's theorem: primes $\in $ NP. Polynomial transformation of languages. NP-complete languages. Cook's theorem: SAT is NP-complete. Hipergraph 2-colorability is NP- complete. Graph-3-colorability is NP-complete.

    The communicational equivalents of P, NP, co-NP, their relations.

    Approximating NP-complete problems: Euclidean Travelling Salesman Problem, the (1+\epsilon)-approximating solution of the knapsack problem by Ibarra and Kim.

    Probabilistic prime-test for non-Carmichael numbers. RSA-cryptosystem with public keys.

    Further randomized algorithms. Polynomial identity-checking.

    Better exponential-time algorithms for the largest independent set-problem. The intervall-packing.

    Comparison-networks, 0-1-rule, Batcher-sort. Boolean-circuits: fan-in 2 and unbounded fan-in circuits, depth and size. Computing arbitrary Boolean-functions with exponential size, depth-2 unbounded fan-in circuits. Computing the sum of two $n$-bit numbers in constant depth and polynomial size. Computing PARITY in $O(\log n/\log\log n)$ depth by poly-size, unbounded fan- in circuit.

    The PRAM model of parallel computation. NC class. The PRAM model and Boolean circuits. Matrix-multiplication in parallel. Polynomial multiplication in parallel, Karatsuba-Ofman method. Chistow-method for computing the characteristic polynomial of a matrix in parallel. Consequences: determinant, solving systems of linear equations, inverse matrix. Parallel graph-algorithms.

    Computing the MAX of $n$ numbers in parallel. Sorting on a PRAM.

    Beyond NP. The polynomial hierarchy. PSPACE, PSPACE-completeness.

    Arthur-Merlin games. Interactive proof--systems.