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 Padding arguments.
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[1].
- 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.