CPSC 506, Sept 17, 2012, Joel Friedman

Here are some brief notes on what we will start Sept 24, and continue
to the following week.  Our goals now are:

(1) Understand circuits and formulas, and their role in complexity lower
bounds.

(2) See some of the more famous complexity classes and some complete
problems for these classes.

We shall embark on the first goal below.  I will suggest that each
class participant tackle part of (2).  We should look at classes like:

Poly Hierarchy, RP and BPP (randomized computation), VP and VNP (Valiant's
algebraic analog of P and NP), #P and the permanent, PSPACE and QSAT=TQBF,
P/poly, others?

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

Goal (1):

The standard approach to P vs. NP is through studying circuit complexity.
The idea is that if, say, 3SAT is in polynomial time, then there are
circuits to compute 3SAT of polynomial size (this is almost immediate from
the proof of the Cook-Levin Theorem).  

A few remarks on this:

(1) For a function f from the positive integers to themselves, let 
CIRCUIT(f(n)) denote the class of languages, L, such that for each
positive integer n there is a circuit of size at most O(f(n)) that
on input x of size n computes "true" iff x is in L.  Then NP is a 
subset of P-CIRCUIT = union over all c of CIRCUIT(n^c).

(2) P-CIRCUIT was historically called "non-uniform poly circuits" or
something like that.  These days one tends to call it P/poly.  The
nice thing about the notation P/poly is that it can be generalized
to things like AlgP/poly (or "VP," Valiant's algebraic analog of P),
AlgNP/poly (or "VNP"), and a number of other interesting classes.
This does, however, add another layer of jargon that may not always
be worth the effort.  The textbook prefers P/poly; intuitively this
mean a computation in P that has access to poly advice.

(3) A superpolynomial lower bound to circuit sizes for 3SAT would
resolve P vs. NP, and a lot of people have spent time trying to
prove such lower bounds.

(4) The class of languages in NP is countable.  The class P-CIRCUIT (i.e.,
P/poly) is uncountable (any function with values in {0,1} that depends only on
the length of a string has polynomial size circuits).  Hence P-CIRCUIT is
strictly larger than NP.

(5) A formula is a weaker notion of a circuit: formulas can be viewed
as rooted trees with variables and constants at the leaves, and operands
at the interior nodes; a node computes a function of its leaves, and 
passes its function to its (unique) parent.  In contrast, a circuit is
similar, except that it can pass its function to more than one "parent";
i.e., a circuit is like a formula, except that it is based on a directed
acyclic graph instead of a tree.

(5') There are a number of standard relationships between the depth and
size of formulas and circuits.  For example, the minimum formula depth
for a function is the same as the minimum circuit depth.  For another,
one can balance a formula (at least in many contexts) at the cost of
at most roughly squaring its size.  It follows that for a formula, its
minimum depth and the log of its minimum size within constant factors
of each other.

(5'') People have had some success proving n^2 and n^3 lower bounds for
formula size in certain contexts.  And people have tried quite hard.
All bounds for classical Boolean or algebraic computations without
some restrictions (e.g., monotone, constant depth but unbounded fan-in, etc.)
are within a constant of the immediate bounds (i.e., n for size, log_2(n)
for depth).