IIT Kharagpur

Department of Computer Science and Engineering

Computational Complexity (Autumn 2005) (3-0-0) 3 credits

PG/UG numbers CS60049/CS40007

Updated November 11, 2005

------------ Books and References:

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.

====================

Registrants:

=======================

Subhankar Mitra (02CS3016), Anil Kumar (02CS1034), Lalit Narayan Paswan (02CS3004), Santosh Biswas (04CS9707), Debabrata Pani (02CS1016), Rahul B. Gokhale (05CS6008), Sushmit Kumar Jha (02CS), Balakaushal Damaraju (05CS6002).

===============================

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.

Lectures on July 21 and 22

===========================

We discussed the scope of this course and introduced basic notions and objectives. We discussed the notion of a problem and its input and output encodings and, independently, definitions and capabilities of machines in terms of memory usage and access, nondeterminism, alternation, randomization or simply deterministic execution. Allusion was made to quantum computing as different from usual classical computing and the presence of high parallelism in quantum computing. We also considered the notion of reducibility between problems with examples from satisfiability and integer linear programming and how upper/lower bounds on complexity measures can be inherited between problems due to reducibilities. We also revised the basic definitions of time complexity and the big-Oh notation.

==================================

Lecture on July 28.

===========================================

It is worthwhile studying the amount of compression required on tape so that an S(n)-space bounded acceptor for a certain language L may be simulated by a c.S(n)-space bounded acceptor for the same language for any given c>0. It turns out that a lower bound of 2/c suffices, that is, we need to pack every 2/c cells of the first machine into one cell in the second machine. Packing certainly makes the finite state control more complex. It is also instructive to note that languages accepted in S(n)-space bounded computations can be also be accepted by halting S(n)-space bounded computations. To show this, we may use an S(n) space counter, counting in a large but constant base and counting the number of steps to see if the count exceeds the number of all possible configurations of the initial machine. In this manner, the simulating machine can be halted if configurations start repeating.

===================================================

Lecture on July 29.

===============================

Compressing the tape can also lead to requisite speedups. To make computations c times faster, c>0, we may require compressing m cells of the simulated machine into one cell in the simulating machine, where m>16/c. This works provided the time complexity T(n) of the simulated machine is superlinear.

Getting back to space complexity, it is easy to see the kinds of languages accepted by TMs with (i) constant space and (ii) linear space. The addition of non-determinism makes the situation interesting. It is easier to see that the classes are closed under complementation in the determinsitic cases. For the non-deterministic cases, one needs to take more care. These issues and deterministic simulations of space-bounded computations will be the themes of a few subsequent lectures.

========================================================

Reading and study exercises.(References to HU79.)

===========================================

(1) Example 12.1, tape compression Theorem 12.1, reduction in the number of tapes Theorem 12.2, Exercise 12.2 and Theorem 12.3 on linear speedup.

(2) Theorems 12.5 and 12.6, reduction in the number of tapes for time complexity.

=========================================================

Assignment #1: Due August 16, 2005

==========================================================

Exercises 12.1, 12.2, 12.3, 12.10.

=====================================================

Lecture on August 1

================================

After revision of previous day's lecture, we started on definitions of classes of languages characterized by S(n) space (or T(n) time) bound. We also stated what co-C was for a class C, thereby defining co-NP from NP and co-DSPACE(S(n)) and co-NSPACE(S(n)). We also stated the L, NL, P, NP and PSPACE telescope and argued using space hierarchy theorem that there is a separation or proper containment somewhere in the telescope. Finally, we went about developing ideas used for deterministic simulation of space classes with quadratic blow-up in space complexity.

========================================

Lecture on August 2

=================================

Deterministic space simulation, Savitch's theorem. ================================

Lecture on August 5

================================

It is worthwhile considering problems where we wish to reverse the acceptance criterion, thereby designing a machine M' that accepts the complement language L' of the language L accepted by a machine M. We consider S(n) (S(n)>= log n) space-bounded machines M and their accepted languages for inputs of length n. We wish to show that L' is in NSPACE(S(n)) if L is in NSPACE(S(n)), ie., M (M') accepting L(L') can be both S(n) space-bounded. This certainly holds for the deterministic case. This non-deterministic case is slighty involved and makes nice use of a technique popularly called "inductice counting". Like in the proof of Savitch's theorem, we again make heavy application of space reuse for various guesses. In addition, we also perform some clever checks and bookkeeping.

Suppose we were able to determine the cardinality s(i) of the set S(i) of vertices reachable by i or less than i hops from a specified starting vertex in a directed graph in non-deterministic log m space, for i=1,2,...,m-1. We know that s(0)=1, and m is the number of vertices of the graph. If such were the case than applying this result to the configuration graph of the NSPACE(S(n)) machine M accepting L, on the input string x, would mean setting m=c^S(n) for some c>2. While determining s(1), s(2), ..., s(m-1), if we encounter any accepting ID or configuration of M, then instead of accepting we must reject and if we finish computing upto s(m-1) and do not reach any accepting ID of M, then we must accept. Such a machine M' will be able to accept the complement L' of L in S(n) space non-deterministically.

Now we must show how the counts s(1), ..., s(m-1) are computed. We would use induction, computing s(k) from s(k-1), for k=1 through m-1.

=========================================

Lecture on August 12.

========================

It is necessary to see how much separation in space resource leads to acceptance of new languages. It turns out that a strictly asymptotically larger space does the job. Technically, if inf 1/n-->0 (S1(n)/S2(n)) is zero, then DSPACE(S1(n)) is a proper subset of DSPACE(S2(n)). The proof goes by constructing an S2(n)-space bounded DTM M that takes a sufficiently large input w so that M halts accepting w if and only if S1(n)-space bounded M_w does not accept w. This diagonalization argument is feasible for every S1(n)-space bounded machine, irrespective of its number t of tape symbols; if there are t tape symbols, M_w will require at most log t times S1(n) space, which is indeed dominated by S2(n) inspite of arbitrary choice of t, by choosing a sufficiently long w of length n. This choice is possible due the the condition "inf 1/n--> (S1(n)/S2(n)) is zero" and the fact that for each TM we have an infinite number of encodings, of increasing sizes. Thus, for every S1(n)-space bounded machine N, we have a large enough w of length n, such that, M_w=N accepts w in S1(n) space if and only if M simulating N=M_w on w, rejects w. So, each S1(n)-space bounded machine differs from S2(n)-space bounded machine M in at least one input w, establishing the result of separation.

================================

Lecture on August 16.

========================

Revision of space hierarchy theorem and extension to time hierarchy theorem.

Introduction to the translation lemma.

=====================================

Lecture on August 19.

========================

The translation lemma and finer hierarchy results.

=====================================

Lecture on August 23.

========================

Discussion and problem session based on Assignment 1 and related problems.

==================================

Lecture on August 26

========================

Sublogarithmic space: (i) demonstration of a language that is not regular (in DSPACE(O(1))), but is in DSPACE(log log n), (ii) allusion to the result, DSPACE(O(1))=DSPACE(o(log log n)) [This is a reading/study exercise].

Introduction to the problem of impossibility of simulating a linear time computation accepting language L with a two-tape DTM using a one-tape DTM using o(n^2) time and accepting L.

==================================

Lecture on August 29

========================

Introduction to deterministic logspace reductions, P-completeness and the P-completeness of the circuit value problem (CVP).

==================================

Class on September 2

========================

Class test, also take home as Assignment #2, submission by September 5.

=================================

Assignment #3: Due date September 10, 2005

=====================

(i) Exercises 12.5 through 12.10.

(ii) Exercises 12.13 through 12.16.

============================================

==================================

Lecture on September 5

========================

Problems and discussions on non-determinism and complement classes.

==================================

Lecture on September 6

========================

Padding arguments for results like the translation lemma: P<>DSPACE(n), etc.

==================================

Lecture on September 26

========================

NP-completeness of decision versions of stable set, vertex cover and clique problems.

Introduction to Interactive Protocols; private coins protocol for NON-ISO (graph non-isomorphism).

==================================

Lecture on September 27

========================

Formal definitions of Arthur-Merlin games and Interactive protocols.

==================================

Lecture on September 30

========================

IP for NON-ISO and Zero-Knowledge protocol for graph 3-colorability.

==================================

Lecture on October 4

========================

Discussions in NP-completeness of Integer Programming, membership in NP.

==================================

Lecture on October 7

========================

Definitions of BPP, RP and co-RP; the significance of these definitions; comments on reduction of error probability.

==================================

Lecture on October 18

========================

Pratt's succint primality certificate; proper inclusion of NL in space classes; simulation of space classes using time classes. Reading exercises: NP membership proof for integer programming; matching algorithms in general and bipartite graphs; approximations for MAXCUT, MINLA, set cover, vertex cover, etc.; definitions of alternation and classes therein; definition of PH.

===============================================

==================================

Lecture on October 21

========================

Discussions on BPP amplification and NP-completeness of Knapsack from ExactCover by 3 sets.

==================================

Lecture on October 24

========================

Inclusion relationships between NC1, L, NL and NC2; definition of Aternation and Alternating Turing Machines; definition of QBF.

==================================

Lecture on October 25

========================

Presentation of proofs of NC1 subset of L, NL subset of NC2 and NL-completeness of 2SAT and REACHABILITY.

-------------------------------------------------

Assignment # 4. [Submissions by November 7, 2005]

(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 #5. Submissions by November 15, 2005.

(1) Show that context-free emptiness is P-complete.

(2) Show that deterministic logspace computations can be done in polynomial time. What about non-deterministic logspace? Why and how?

(3) Show that REACHABILITY is NSPACE(log n)-complete.

(4) Is NTIME(2^n) a proper subset of NTIME(3^(n log n))? Why?

(5) Is Integer Linear Programming NP-hard? In NP? Why?

-------------------------------------------------------------------------

Assignment #6. Submissions by November 20, 2005.

(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) 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 #7. Submissions by November 25, 2005.

(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 #8. Submissions by November 30, 2005.

(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.

--------------------------------------------------------------------------

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

==================================

Lecture on October 31

========================

PH, definition and collapse to a finite level on having a complete problem; complete classes at levels of PH; QSATi.

==================================

Lecture on November 8

========================

PP and its relation with NP; polynomial size circuits for languages in the class P and the reduction of languages in NP into satisfiable 3-CNF formulae (Cook's theorem); differences between BPP and PP in terms of probability amplification.

==================================

Lecture on November 11

========================

Uniform family of polynomial size circuits for BPP; a counting argument leading to the construction. The derandomization of BPP into the second level of PH.

==================================