Information Technology Reference
In-Depth Information
·
=
than VF; that is, VNP
VP. For clarity, let us agree to temporarily refer to
these two definitions as VNF (or VNP
e
) and VNP. However, Valiant [
Va l 8 2
]showed
that these two classes are in fact the same, so just VNP will do. The proof involves
showing that VP is contained in
·
VF. And it is of course easier to show upper
bounds with the definition of VNP rather than VNF.
Now Valiant observed that not only
is
p
-definable. This
should be similar to showing that the 0-1 permanent is in #P, right? Almost. We
are dealing with symbolic polynomials, so we do not have the liberty of looking at
an input value and deciding what to do next. Still, the basic idea is the same. For
a statement
S
,let
(
Det
n
)
,even
(
Perm
n
)
denote the 0-1 valued Boolean predicate that takes value 1
exactly when
S
is true. Then
[
S
]
⊡
⊤
⊛
⊞
−
Y
is a 0
1
permutation
matrix
n
n
n
⊣
⊦
·
⊝
⊠
Perm
n
=
x
i
˃(
i
)
=
Y
ij
x
ij
˃
∃
S
n
i
=
1
n
×
n
i
=
1
j
=
1
Y
∃{
0
,
1
}
⊡
⊤
Y
is a 0
1
permutation
matrix
−
⊣
⊦
=[
]
Y
has at least one 1 in each row
Y
has at most one 1 in each line
(line = row or column)
×[
]
⊛
⊞
⊛
⊞
⊝
⊠
n
n
⊝
⊠
=
Y
ij
(
1
−
Y
ij
Y
km
)
i
=
1
j
=
1
(
i
,
j
)
=
(
k
.
m
)
;
i
=
k
or
j
=
m
Clearly, the polynomial family
⊛
⊞
⊛
⊞
⊛
⊞
⊝
⊠
n
n
n
n
⊝
⊠
⊝
⊠
g
n
=
Y
ij
(
1
−
Y
ij
Y
km
)
Y
ij
x
ij
i
=
1
j
=
1
i
=
1
j
=
1
(
i
,
j
)
=
(
k
.
m
)
;
i
=
k
or
j
=
m
)
=
Y
∃{
0
,
1
}
n
3
has formulas of size
O
(
)
, and Perm
n
(
√
x
g
n
(
√
x
,
Y
)
,so
(
Perm
n
)
is in
n
×
n
VNP.
So we have some families in VP (even VF), and some in VNP but maybe not in
VP. How do we compare families? For comparing languages, we have many-one
reductions and Turing reductions—what is the algebraic analogue? Valiant proposed
projections, a most restrictive kind of reduction when dealing with Boolean classes,
but completely natural in the algebraic context. We say that
g
∃ F[
y
1
,...,
y
m
]
is
a projection of
f
∃ F[
x
1
,...,
x
n
]
if
g
can be obtained from
f
by substituting a
