Introduction to Automata, Languages and Computation, Hopcroft and Ullman, Addison-Wesley, 1979.
Computational Complexity, Papadimitriou, 1994.
Structural Complexity: Volumes I and II by Balcazar, Gabbaro and Diaz.
Considerable weightage will be given on class tests and home assignments. Knowledge of elementary data structuring and progamming is required to register for this course. A prerequisite is Design and Analysis of Algorithms or its equivalent. In addition, a course on Formal Languages and Automata Theory or its equivalent is also a prerequiste for this course. The syllabus for this course is available in the department and in the UP and PG course brochures. Although the course has a PG number, all UG and PG students with proper prerequisites can credit this course.
-------------------------------------------------------------------------------
Lectures Tuesdays 7:30 am to 9:25 am, Thursdays 11:30 am and 4:30 pm
-------------------------------------------------------------------------------
Please note that delays in submitting assignments may suffer some erosion in the credits earned for them in some cases. It is therefore essential to work regularly and complete all assignments in time, as far as possible.
----------------------------------------------------------------------
Topics covered so far (until April 3, 2003) in roughly reverse order:
Use of pairwise independent psuedorandomness to reduce the number of random bits in BPP and RP success probability amplification;
Arthur-Merlin games, Arthur-Merlin protocol for graph non-isomorphism using random linear hash functions;
zero-knowledge interactive protocol for graph 3-colorability;
interactive protocols for graph non-isomorphism, languages in NP and BPP;
the derandomization of BPP into the second level in PH;
the collapse of PH on having a complete problem, the membership of circuit minimization query in the second level of PH, the i quantifiers' characterization for Sigma_i and Pi_i of PH_i;
the random walk result showing that UNDIRECTED REACHABILITY is in RL, the random walk result showing that 2SAT is in RP;
the notion of zero error probability and the class ZPP, the proof that ZPP=RP intersection co-RP; the closure of BPP and PP under complementation, the containment of NP in PP;
the relationships between L, NC_1, NL and NC_2;
the NP-completeness of CIRCUIT-SAT and SAT, the P-completemness of CIRCUIT VALUE problem;
the simulation of non-determinisn in polynomial space (Savitch's theorem), the NSPACE(log n)-completeness of REACHABILITY;
space and tme hierarchy results;
the halting of space bounded computations;
the Chomsky hierarchy seen as Turing Machines with restricted powers;
----------------------------------------------------------------------
Assignment # 1. Submissions in hardcopy handwriten sheets by Janunary 28, 2003, 4:30 pm
(1) Show that the problem of graph non-isomorphism is solvable in polynomial space. Show that the graph isomophism problem is in NP. Note that subgraph isomorphism is NP-complete; produce a proof for this result too.
(2) Show that context-free emptiness is in P.
(3) Show that NSPACE(n) is precisely the set of context sensitive languages.
(4) Show that DCSL=co-DCSL.
(5) We wish to do triangulations of (i) n-sided simple polygons as well as (ii) arbitrary point sets of cardinality n, in the plane. Are these in P? Why? Suppose we wish to find a triangulation in cases (i) and (ii) with minimum ink (triangulation edges' lengths added up is minimised, saving ink !). Do these problems remain in P? become NP-complete? get into NP? Explain and discuss in detail.
--------------------------------------------------------------------------
Assignment #2. Submissions by Feb 10, 2003.
(1) Show that CIRSAT (Circuit Satisfiability) is logspace reducible to SAT (Satisfiability).
(2) Show that determining whether a given graph has an independent set of size n/3 is NP-complete. Here, n is the number of vertices of the graph.
(3) Show that context-free emptiness is P-complete.
(4) Show that deterministic logspace computations can be done in polynomial time. What about non-deterministic logspace? Why and how?
(5) Show that REACHABILITY is NSPACE(log n)-complete.
(6) Is NTIME(2^n) a proper subset of NTIME(3^(n log n))? Why?
(7) Is Integer Linear Programming NP-complete? Why?
-------------------------------------------------------------------------
Assignment #3. Submissions by Feb 19, 2003.
(1) Show that NP is not the same as DSPACE(n). Show also that P is not the same as DSPACE(n).
(2) Show that checking of palindromes is in DSPACE(log n).
(3) Is primality testing possible in DSPACE(n)? DSPACE(log n)? Why?
(4) Show that NC1 is a subset of L and NL is a subset of NC2.
(5) Determine whether the following problem is in NC. Given a set S of n points in the plane, determine whether the there is a pair of points in S having a separation of no more than a distance of C>0 where C is a constant.
-------------------------------------------------------------------------
Assignment #4. Submissions by March 19, 2003.
(i) Show that the probability of false negatives in a Monte Carlo algorithm can be reduced to an inverse exponential in a polynomial of the input size with polynomial blowup in time complexity (even if the probability of false negatives was initially as high as (1-1/p(n)), where p(n) is a polynomial).
(ii) Show that for languages L in ZPP, membership in L can be tested in expected polynomial time.
(iii) Show that if SAT is solvable probabilistically with bounded errors in polynomial time, then SAT is also solvable using a Monte Carlo method in polynomial time.
(iv) Show that SAT is solvable in probabilistic polynomial time by a machine which decides by majority.
(v) Show that the class of languages decided by majority in polynomial probabilistic time is closed under complementation.
(vi) Show that the class of languages decided by absolute majority in polynomial probabilistic time is also closed under complementation.
-------------------------------------------------------------------------
Assignment #5. Submissions by March 31, 2003.
(i) Demonstrate two problems, one each for the second level and the third level in PH, the polynomial hierarchy. (Choose problems of your own, not the corresponding SAT problems.)
(ii) Show that PH is a subset of PSPACE.
(iii) Show that the error probability in deciding languages in BPP can be reduced to an inverse exponential in a polynomial of the input size with only a polynomial blowup in running time.
(iv) Show that any language decided by success probability (1/2)+e, 1/2>e>0, is in BPP.
--------------------------------------------------------------------------