IIT Kharagpur

Department of Computer Science and Engineering

Computational Complexity (Autumn 2021) (3-1-0) 4 credits

UG number CS41103

Updated November 13, 2021

Lectures online Wednesdays 10 am, Thursdays 9 am and Fridays 11 am. (Slot F4)

Coverage in CS41103 in Autumn 2021 Slides for CS41103 in Autumn 2021

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

Introduction to Automata, Languages and Computation, Hopcroft and Ullman, Addison-Wesley, 1979.

Computational Complexity, Papadimitriou, 1994.

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach.

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

Objectives and scope of the course CS41103 Computational Complexity

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

For doing this course, some algorithmic and discrete structures background is useful and necessary. Those we have been familiar with automata theory, formal languages, computation theory and similar topics will find such background relevant and useful. The objective of this course is essentially to understand the quantitative limits of resource bounded computations, where time and space are the most common types of computational resources. Based on the amount of resources permitted, one studies the classes of problems that can be solved within those resource bounds, essentially classifying problems in to what we call complexity classes. Time resource or computational time, is what determines classes P and NP, where the class NP uses nondeterminism and P uses only deterministic computations; we do not know whether P is a proper subset of NP. Similarly space complexity classes like PSPACE and NL are such that NL is a proper subset of PSPACE, and both these two space bounded classes are closed under complementation. We know that the class P is closed under complementation but we do not know whether the class NP is closed under complementation. The class P has ``complete'' problems such as the CVP (the circuit value problem), whereas the class NP has ``complete'' problems like the SAT and the 3SAT problem. Such complete problems in a way represent the level of richness of the classes in terms of the underlying machine models and the computational resources they require to ``solve'' or ``decide'' the complete problems. Though some of these classes are known to have wonderful and useful probabilistic characterizations, we will also see probabilistically defined complexity classes that are not known to have complete problems in the usual sense, even though with some modifications like introducing ``promises'' or ``approximations'', it is possible to sometimes define ``complete'' problems for such ``semantic'' complexity classes. The most useful and significant probabilistic class BPP is believed by many to be identical to the deterministic class P. We know however that BPP is well within the second level in PH, the polynomial hierarchy.

Probabilistic characterizations as well as complete problems exist for the space class PSPACE, and the time class NP. For time class P, there are nice boolean circuit characterizations.

Coverage in CS41103 in Autumn 2021

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

Registration: This course is open to all UG students and dual degree students in the institute provided the pre-requisites are met. The slot for the course is F4.

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

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

CS41103 COMPUTATIONAL COMPLEXITY L-T-P: 3-1-0, Credits: 4 (as in cse website)

Computational Models (machine models, logic); Problems, computability, Algorithms, Resources, and Complexity; Turing machines (time and space bounds, nondeterminism); Logic (Boolean logic, circuits, first and second order logic); Complexity classes (hierarchy theorem, reachability, P, NP, Co-NP); Reduction and completeness; Randomized computation; Approximability; Cryptography and protocols; Parallel Computation; Polynomial Hierarchy; Logarithmic space; Polynomial space; Exponential time and space.

References

==========

Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Longman.

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata, Languages and Computation, Addison-Wesley, 1979.

J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, Volumes I and II, Springer.

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

Some coverage in the 2005 offering of a similar PG level course (CS60049 with the same name Computational Complexity) is stated below.

CS41103 is somewhat different from CS60049. Not all the coverage in computational complexity theory of CS60049 is required in CS41103. However, registrants may choose seminars or term papers or study topics for discussions from topics in computational complexity theory as stated below in the coverage of CS60049 in 2005.

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.

Coverage in the 2005 course CS60049

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

Registrants in Autumn 2005

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

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

Lectures on July 21 and 22, 2005

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

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, 2005.

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

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.

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