Information Technology Reference
In-Depth Information
class better. If a natural family is complete for a class, then this is evidence that the
class itself is natural.
Valiant started off with a proof that Perm is VNP-complete. He also showed
that polynomial families associated with a number of NP-complete languages are
complete for VNP under
p
-projections. So let us agree that VNP is a natural class.
What about VP? The family that naturally contrasts with Perm is Det, but Det is
not yet known to be complete for VP (unless we allow
qp
-projections; that is not
quite satisfactory). If this turns out to be the case, it will solve a major open problem,
showing that polynomial-degree polynomial size circuits are no more powerful than
polynomial-size branching programs VBP. VBP seems a natural enough class, and
Det and many other families are complete for it.
So what problems are complete for VP? One can construct a canonical family
complete for VP. By canonical, I mean something similar to saying that
1
t
{≈
M
,
x
,
ₒ|
M
is an NDTM that accepts
x
in
t
or fewer steps
}
is NP-complete. Undoubtedly true, but it doesn't give any new intution about what
NP is about. In the case of VP, the canonical family is not so trivial to construct (but
not very difficult either).
The first description, with a very general completenes result, appears in [
Bür00a
]
classes VP
h
and VNP
h
have complete families with respect to
p
-projections. Since
VP
h
VP and VNP
h
=
=
VNP whenever
h
itself is in VP, this gives families
complete for VP and VNP as well. (In fact, it shows the existence of VNP-complete
families, independent of Valiant's original proof.) These complete families compute
homogeneous components separately, to keep the degree small, and then add up the
required parts. They are constructed by first defining
generic polynomials
, and then
defining the appropriate projection/substitution. The generic polynomials capture the
canonical notion referred to above.
Later, a more direct construction tailored for VP (as opposed to VP
h
and VNP
h
for all
h
) was described by Raz [
Raz10
], and also appears in [
SY10
]. Here, the proof
of hardness exploits the fact that we can perform depth reduction on VP circuits.
(This was not needed in Bürgisser's proof.) Roughly, here's how it goes: For each
natural number
N
, consider a circuit
C
N
with nodes arranged in 2 log
N
+
1 layers
numberd 0
2log
N
. All even layers have exactly
N
nodes, and compute poly-
nomials
g
i
,
j
where
i
is the layer number,
j
,
1
,...,
. Odd layers are used to build these
polynomials. At layer 0, the polynomials are just distinct variables,
g
0
.
j
∃[
N
]
=
x
j
.At
=
k
,ʲ
∃[
N
]
g
i
,
k
·
g
i
,ʲ
·
higher layers, we have an inductive definition:
g
i
+
1
,
j
y
i
,
j
,
k
,ʲ
,
where the
y
i
,
j
,
k
,ʲ
are new variables. Thus the nodes at the odd layers are the fanin-
3
nodes with
large fanin. (We can reduce the fanins to 2 later; it won't change the polynomial
computed.) The polynomial computed by this circuit at
g
2log
N
,
1
is
p
N
. The total
number of variables is
O
×
nodes, and nodes at even layers (other than the 0 layer ) are
+
N
3
log
N
N
3
log
N
(
)
, and the circuit is also of size
O
(
)
.
The degree of
p
N
is 2
N
−
1. So
(
p
N
)
is in VP. Why is it VP-hard? Take any family
in VP. By the depth reduction of [
VSBR83
], it can be computed in VSAC
1
.The
(
f
n
)
