Information Technology Reference
In-Depth Information
F
=
x
1
x
2
+
value in
Y
for each variable in
X
. (For instance, if
f
x
3
x
4
, then the
y
2
y
3
,2
y
2
.But
y
1
y
2
,
following are all projections of
f
:
y
1
+
y
2
,
y
1
y
2
+
5,
y
1
y
2
+
y
3
are not, because a projection cannot increase the degree or number of
monomials.) Further, we say that a family
y
1
+
y
2
+
if
each
g
n
is a projection of some
f
m
for an
m
not too far from
n
. That is, there is a
polynomially bounded function
t
, and each
g
n
is a projection of
f
t
(
n
)
(g
n
)
is a
p
-projection of a family
(
f
n
)
. If we allow
t
to be quasi-polynomially bounded, we obtain
qp
-projections.
Using these notions of reductions, we have the usual notions of hardness and
completeness for algebraic classes. Here's what Valiant showed:
1.
(
Det
n
)
is hard for VF under
p
-projections (and is known to be in VP).
2.
is complete for the class of quasi-polynomial size formulas VQF under
qp
-projections.
3. Over fields with characteristic other than 2,
(
Det
n
)
is complete for VNP under
p
-projections. Over fields of characteristic 2, Perm
n
equals Det
n
and hence is in
VP and VQF.
4. Polynomial families associated with a number of NP-complete languages are
complete for VNP under
p
-projections.
(
Perm
n
)
The first two follow from a proof that a polynomial computed by a size
s
formula
is a projection of Det
s
+
2
. (It uses the combinatorial definition of determinant. as the
signedweighted sumof cycle covers in an associated graph.) The hardness of
Perm
n
)
for VNP mirrors the hardness of the Boolean permanent for the counting class #
P
.
As in the case of the upper bound, additional care is needed to take into account non-
access to an input instance and fully symbolic computations; in particular, the proof
requires a multiplicative inverse of two and hence fails over fields of characteristic
2. See [
Va l 7 9
,
BCS97
,
Bür00a
] for various versions of these proofs. See [
Blä13
]for
a simplified gadget construction.
(
4.3 The Current Status
We now know much more about the classes VF, VP, VQP, VNP defined above, and
about other similarly defined classes. Let's review these results one by one.
Say that a family of polynomials
is a
p
-family if the number of variables in
f
n
and the degree of
F
are polynomially bounded functions of
n
. We only consider
p
-families.
Recall that VP consists of
p
-families with polynomial-sized circuits. Also note
that algorithmically, circuit size roughly corresponds to number of processors needed
in a parallel algorithm (associate one processor per gate), while circuit depth—the
length of a longest path from the output node to an input node—corresponds to
parallel time.
A clever construction due to Hyafil [
Hya79
] shows that any polynomial of degree
D
in
M
variables, computable by a circuit of size
t
, can be computed in parallel time
O
(
f
n
)
D
2
t
(
×
(
+
))
log
D
log
M
. This is a depth-reduction of the circuit, and generalises
