# Computational Complexity (Spring 2017)

This course describes attempts to answer a fundamental question of CS namely: What can computers solve efficiently?

Some Bibliography:

While the course does not follow one book in a precise order, most of the material can be found in the following two books (that are available online). I will point to relevant section in the books when teaching the material.

Some of the topics (at least in the beginning of the course) are also covered in the following books.

• Computational Complexity by Christos Papadimitriou.
• Introduction to the theory of computation by Michael Sipser.

Requirements:

There will be an exam at the end of the course. During the lectures I will sometimes present questions and challenges for you to think about. You are encouraged to work on these questions.

Exercises:

These exercises are not for submission. However you are strongly encouraged to solve them.

-        Exercise 1 (on space complexity)

-        Exercise 2 (on diagonalization and the polynomial time hierarchy)

-        Exercise 3 (on circuits and randomized algorithms)

-        Examples of class exams: (1)     (2)     (3)      (4)

Take Home Exam:

If you came to class regularly, you may ask for permission to do a take home exam (instead of an exam, you cannot do both).

Here is the take home exam.

If you are interested in taking the take home exam, please write to me and send me:

1.    Your name and ID.

2.    How many lectures did you miss?

3.    Why you want to do a take home exam, and not a class exam.

You must receive an approval from me in order to do the take home exam.

Material:

• Space complexity. The material can be found in Part I chapter 4 in Arora-Barak, or Chapter 5 in Goldreich. Most of this material is also available in Sipser's and Papadimitriou's books.
• Definition of TMs that run in space << n.
• Example: Addition in space O(log n).
• Composition of functions that are computable in logspace.
• 3-SAT in linear space.
• Definition of L, NL, PSPACE, NPSPACE.
• Example: directed connectivity in NL.
• A randomized algorithm for undirected connectivity in logspace (no proof yet)
• NSPACE(s(n)) in TIME(2^{O(s(n))}) (configuration graphs). (corollary: NL in P).
• Savich's theroem: directed connectivity in space log^2 n.
• Corollary: NSPACE(s(n)) in SPACE(s(n)^2). (implies: NPSPACE=PSPACE).
• Definition of quantified Boolean formula and the language TQBF.
• TQBF is PSPACE complete.
• NL completeness.
• dPATH is NL complete.
• Definition of NL by certificate verification.
• NL=co-NL.
• 2-SAT in NL (sketch only).

• Diagonalization.
• Time complexity, quick review.
• Deterministic time hierarchy theorem.

o   The generality of the argument: the deterministic space hierarchy theorem.

o   Why the argument doesn't give a nondeterministic time hierarchy theorem.

o   The non-deterministic time hierarchy theorem (delayed diagonalization).

o   Weakness of diagnolization: results proven this way hold for any oracle.

o   An oracle A such that NP^A <> P^A. Implies impossibility of proving NP<>P by direct diagonalization.

o   The notion of relativizing statements and proofs.

o   The statement NP=P and NP<>P are non-relativizing.

·       The polynomial time hierarchy

o   Definition with quantifiers and definition with oracles (equivalence is an exercise).

o   The hierarchy collapses if PH has a complete problem.

o   The hierarchy collapses if Sigma_i = Pi_i.

o   Time space tradeoffs: NTIME(n) not contained in TISP(n^{1.2},n^{0.2}).

·       Circuits

• Definition of Boolean circuits and families of Boolean circuits. The class PSIZE.
• Thm: For every TM M that runs in time t(n) and input length n there is a circuit C of size ct(n)^2 that is equivalent to M on inputs of length n.
• Discussion on nonuniform computation. Circuits can compute undecidable languages.
• Uniform circuits and the equivalence of L-uniform polynomial size circuits to P.
• Nonuniform Turing machines, the class P/poly and PSIZE=P/poly.
• Approach: Showing that NP<>P by showing that NP isn't in P/poly.
• Karp-Lipton theorem: NP in P/poly implies PH=\Sigma_2.
• Reminder: decision versus serach versions for problems in NP.
• If NP in P/poly then NP search problems can be solved by poly-size circuits.

• The class NC and its relation to distributed computing.
• Parity is not in AC0. (We saw the proof by Razborov-Smolensky, see for example Arora-Barak Part II chapter 13, section 13.2).
• Natural properties and the Razborov-Rudich negative result (statement only).
• Randomized Algorithms (Examples).
• Example: Polynomial identitiy testing.
• Example: Perfect Matching in randomized NC.
• Example: Primality testing (outline only).
•  Definition of probabilistic algorithms and complexity classes: BPP, RP and relationships between them.
• Discussion: The power of probabilistic algorithms. We think that BPP=P but do not know to show that BPP<>NEXP.
• BPP in P/poly
• BPP in Sigma_2. Corollary if NP=P then BPP=P.
• Hardness vs. Randomness (sketch only).
• Interactive proofs.
• Definition of interactive proofs and the class IP.
• Observations regarding IP:
• NP in IP in PSPACE.
• IP = NP when verifier is deterministic.
• Prover's optimal strategy can be found in PSPACE.
• Amplification of success probability (both in parallel and sequentially).
• Graph non isomorphism in IP.
• coNP in IP:
• Arithmetization.
• The sumcheck protocol.
• What is nonrelativizing here?
• IP=PSPACE. Modifications required to the sumcheck protocol.
• Discussion: public coins and private coins.
• Theorem: Any private coin proof can be simulated by a public coin proof with O(1) additional rounds. (We only saw a sketch for GNI).
• The class AM=IP[O(1) rounds and public coins].
• MA in AM and AM[k]=AM.
• Corollary: If Graph isomorphism is NP complete then PH collapses.

·        Probabistically checkable proofs

o   Definition of the class PCP(r,q).

o   Proof that NP is in PCP(poly(n),O(1)).

• The PCP theorem: NP=PCP(O(log n),O(1)). (Statement only)
• Approximation algorithms. (Example MAX-3-SAT has a a 7/8 approximation algorithm when all 3 literals are different).
• The problem max-q-CSP.
• Relationship between PCP and hardness of approximation: Max-q-CSP cannot be approximated within a constant factor if NP<>P.
• The PCP theorem as a gap amplifying reduction.
• Discussion: PCP as a robust version of the Cook-Levin theorem and intuitive connection to error-correcting codes.