Lecture 1:
The P vs NP Question.
We review the fundamental question of computer science,
known as the P versus NP question:
Given a problem whose solution can be verified efficiently
(i.e., in polynomial time),
is there necessarily an efficient method to actually find such a solution?
Loosely speaking, the first condition (i.e., efficient verification)
is captured in the definition of NP, and the second in that of P.
The actual correspondence relies on the notion of self-reducibility,
which relates the complexity of determining whether a
solution exists to the complexity of actually finding one.
Lecture 2:
NP-completeness and Self Reducibility.
We prove that any relation defining an NP-complete language
is self-reducible.
This will be done using the SAT self-reducibility (proved in Lecture 1),
and the fact that SAT is NP-Hard under Levin Reductions.
The latter are Karp Reductions augmented by efficient transformations
of NP-witnesses from the original instance to the reduced one,
and vice versa.
Along the way, we give a simple proof of the existence of NP-Complete
languages (by proving that Bounded Halting is NP-Complete).
NP-completeness.
Lecture 3:
More on NP and some on DTIME.
In the first part of this lecture we discuss two properties
of the complexity classes P, NP and NPC:
the first property is that NP contains problems which are neither
NP-complete nor in P (provided NP not equal P),
and the second one is that NP-relations have optimal search algorithms.
In the second part we define new complexity classes
based on exact time bounds, and consider some relations between them.
We point out the sensitivity of these classes to the specific model of
computation (e.g., one-tape versus two-tape Turing machines).
Lecture 4:
Space Complexity.
We define ``nice'' complexity bounds; these are bounds which can be
computed within the resources they supposedly bound (e.g.,
we focus on time-constructible and space-constructible bounds).
We define space complexity using an adequate model of computation in
which one is not allowed to use the area occupied by the input for
computation. Before dismissing sub-logarithmic space, we present
two results regarding it (contrasting sub-loglog space with loglog space).
We show that for ``nice'' complexity bounds,
there is a hierarchy of complexity classes - the more resources
one has the more tasks one can perform.
One the other hand, we mention that this increase in power may not
happen if the complexity bounds are not ``nice''.
Lecture 5:
Non-Deterministic Space.
We recall two basic facts about deterministic space complexity,
and then define non-deterministic space complexity.
Three alternative models for measuring non-deterministic space complexity
are introduced: the standard non-deterministic model, the online model,
and the offline model. The equivalence between the standard
and online models and their exponential relation to the offline model
are proved. We then turn to investigate the relation between the
non-deterministic and deterministic space complexity
(i.e., Savitch's Theorem).
Lecture 6:
Non-Deterministic Logarithmic Space.
We further discuss composition lemmas underlying previous lectures.
Then we study the complexity class NL (the set of languages decidable
within Non-Deterministic Logarithmic Space):
We show that directed graph connectivity is complete for NL. Finally,
we prove that NL = coNL (i.e., NL is closed under complementation).
Lecture 7:
Randomized Computations.
We extend the notion of efficient computation
by allowing algorithms (Turing machines) to toss coins.
We study the classes of languages that arise from various natural
definitions of acceptance by such machines.
We focus on probabilistic polynomial-time machines with
one-sided, two-sided and zero error probability
(defining the classes RP (and coRP), BPP and ZPP).
We also consider probabilistic
machines that uses logarithmic spaces (i.e., the class RL).
Lecture 8:
Non-Uniform Polynomial Time (P/poly).
We introduce the notion of non-uniform polynomial-time
and the corresponding complexity class P/poly.
In this (somewhat fictitious) computational model,
Turing machines are provided an external advice string to aid
them in their computation (on strings of certain length).
The non-uniformity is expressed in the fact that an arbitrary advice
string may be defined for every different length of input.
We show that P/poly ``upper bounds'' the notion of efficient computation
(as BPP} subseteq P/poly), yet this upper bound is not tight
(as P/poly contains non-recursive languages). The effect of introducing
uniformity is discussed, and shown to collapse P/poly to P.
Finally, we relate the P/poly versus NP question to the question of
whether NP-completeness via Cook-reductions is more powerful that
NP-completeness via Karp-reductions. This is done by showing, on one hand,
that NP is Cook-reducible to a sparse set iff NP subset P/\poly,
and on the other hand that NP is Karp-reducible to a sparse set iff NP=P.
Lecture 9:
The Polynomial Hierarchy (PH).
We define a hierarchy of complexity classes extending NP and contained
in PSPACE. This is done in two ways, shown equivalent:
The first by generalizing the notion of Cook reductions,
and the second by generalizing the definition of NP.
We then relate this hierarchy to complexity classes
discussed in previous lectures such as BPP and P/poly:
We show that BPP is in PH, and that if NP subseteq P/poly
then PH collapses to is second level.
Lecture
10: The counting class #P and Approximating it.
The class NP captures the difficulty of determining whether a
given input has a solution with respect to some (tractable) relation.
A potentially harder question, captured by the class #P,
refers to determining the number of such solutions.
We first define the complexity class #P, and classify it with respect to
other complexity classes. We then prove the existence of #P-complete
problems, and mention some natural ones. Then we try to study the
relation between #P and NP more exactly, by showing we can
probabilistically approximate #P using an oracle in NP.
Finally, we refine this result by restricting the oracle
to a weak form of SAT (called uniqueSAT).
Lecture
11: Interactive Proof Systems.
We introduce the notion of interactive proof systems and the
complexity class IP, emphasizing the role of randomness and interaction
in this model. The concept is demonstrated by giving an interactive proof
system for Graph Non-Isomorphism. We discuss the power of the class IP,
and prove that coNP subseteq IP. We discuss issues regarding the number
of rounds in a proof system, and variants of the model such as public-coin
systems (a.k.a.\/ Arthur-Merlin games).
Lecture
12: Probabilistically Checkable Proof (PCP).
We introduce the notion of Probabilistically Checkable Proof (PCP) systems.
We discuss some complexity measures involved, and describe the class
of languages captured by corresponding PCP systems.
We then demonstrate the alternative view of NP
emerging from the PCP Characterization Theorem,
and use it in order to prove non-approximability
results for the problems max3SAT and maxCLIQUE.
Lecture
13: Pseudorandom Generators.
Pseudorandom generators are defined as efficient deterministic
algorithms which stretch short random seeds into longer pseudorandom
sequences. The latter are indistiguishable from truely random
sequences by any efficient observer.
We show that, for efficiently sampleable distributions,
computational indistiguishability is preserved under multiple samples.
We related pseudorandom generators and one-way functions,
and show how to increase the stretching of pseudorandom generators.
The notes are augmented by an essay of Oded.
Lecture
14: Pseudorandomness and Computational Difficulty.
We continue our discussion of pseudorandomness and show
a connection between pseudorandomness and computational difficulty.
Specifically, we show how the difficulty of inverting one-way functions
may be utilized to obtain a pseudorandom generator. Finally, we state and
prove that a hard-to-predict bit (called a hard-core)
may be extracted from any one-way function. The hard-core is
fundamental in our construction of a generator.
Lecture
15: Derandomization of BPP (The NW-generator).
We present an efficient deterministic simulation
of randomized algorithms. This process, called derandomization,
introduce new notions of pseudorandom generators. We extend the
definition of pseudorandom generators and show how to construct a
generator that can be used for derandomization.
The new construction differ from the generator that
constructed in the previous lecture in it's running time (it will
run slower, but fast enough for the simulation). The benefit is that
it is relying on a seemingly weaker assumption.
Lecture
16: Derandomizing Space-Bounded Computations.
We consider derandomization of space-bounded computations.
We show that BPL subseteq DSPACE(\log^2 n),
namely, any bounded-probability Logspace
algorithm can be deterministically emulated in O(\log^2 n) space.
We further show that BPL subseteq SC,
namely, any such algorithm can be deterministically emulated in
O(\log^2 n) space and (simultaneously) in polynomial time.
Lecture
17: Zero-Knowledge Proof Systems.
We introduce the notion of zero-knowledge interactive proof
system, and consider an example of such a system (Graph Isomorphism).
We define perfect, statistical and computational zero-knowledge,
and present a method for constructing zero-knowledge proofs
for NP languages, which makes essential use of bit commitment schemes.
We mention that zero-knowledge is preserved under sequential composition,
but is not preserved under the parallel repetition.
Lecture
18: NP in PCP[poly,O(1)].
The main result in this lecture is NP subseteq PCP(poly,O(1)).
In the course of the proof we introduce an NPC language ``Quadratic
Equations'', and show it to be in PCP(poly,O(1)).
The argument proceeds in two stages: First assuming
properties of the proof (oracle), and then testing these properties.
An intermediate result that of independent
interest is an efficient probabilistic algorithm that distinguishes
between linear and far-from-linear functions.
Lecture
19: Dtime(t) contained in Dspace(t/log t).
We prove that Dtime(t(\cdot)) subseteq Dspace(t(\cdot)/\log t(\cdot)).
That is, we show how to simulate any given deterministic multi-tape
Turing Machine (TM) of time complexity $t$, using a deterministic TM
of space complexity $t/\log t$. A main ingrediant in the simulation is
the analysis of a pebble game on directed bounded-degree graphs.
Lecture
20: Circuit Depth and Space Complexity.
We study some of the relations between Boolean circuits
and Turing machines. We define the complexity classes NC
and AC, compare their computational power,
and point out the possible connection
between uniform-NC and ``efficient'' parallel computation.
We conclude the discussion by establishing a strong connection between
space complexity and depth of circuits with bounded fan-in.
Lecture
21: Communication Complexity.
We consider Communication Complexity - the analysis of the amount
of information that needs to be communicated betwen two parties
that wish to reach a common computational goal. We start with some
basic definitions, considering both deterministic and probabilistic
models for the problem, and annotating our discussion with a few examples.
Next we present a couple of tools for proving lower bounds on the
complexity of communication problems. We conclude by proving a
linear lower bound on the communication complexity of probabilistic
protocols for computing the inner product of two vectors,
where initially each party holds one vector.
Lecture
22: Circuit Depth and Communication Complexity.
The main result presented in this lecture is a (tight) nontrivial
lower bound on the monotone circuit depth of s-t-Connectivity.
This is proved via a series of reductions,
the first of which is of significant importance:
A connection between circuit depth and communication complexity.
We then get a communication game and proceed to reduce it to other such
games, until reaching a game called FORK. We conclude that a lower bound
on the communication complexity of FORK, to be given in the next lecture,
will yield an analogous lower bound
on the monotone circuit depth of s-t-Connectivity.
Lecture
23: Communication Complexity of the FORK Game.
We analyze the FORK game, introduced in the previous lecture.
We give tight lower and upper bounds on the communication needed in a
protocol solving FORK.
This completes the proof of the lower bound on the depth of monotone
circuits computing the function st-Connectivity.
Lecture
24: Average-Case Complexity.
We introduce a theory of average-case complexity which refers to
computational problems coupled with probability distributions.
We start by defining and discussing the classes of P-computable
and P-samplable distributions. We then define the class DistNP
(which consists of NP problems coupled with P-computable distributions),
and discuss the notion of average polynomial-time
(which is unfortunately more subtle than it may seem).
Finally, we define and discuss reductions between distributional problems.
We conclude by proving the existence of a complete problem for DistNP.
Lecture
25: Computational Learning Theory.
We define a model of automoatic learning called
probably approximately correct (PAC) learning.
We define efficient PAC learning, and present several efficient PAC
learning algorithms. We prove the Occam's Razor Theorem, which reduces
the PAC learning problem to the problem of finding a succinct
representation for the values of a large number of given labeled examples.
Lecture
26: Relativization.
In this lecture we deal with relativization of complexity classes.
In particular, we discuss the role of relativization with respect
to the P vs NP question; that is, we shall see that for
some oracle A, $P^A = NP^A$, whereas for another $A$
(actually for almost all other $A$'s) $P^A \neq NP^A$.
However, it also holds that $IP^A \neq PSPACE^A$ for a random $A$,
whereas $IP = PSPACE$
