Information Technology Reference
In-Depth Information
arithmetic circuits that arise when we consider counting classes like #P that count
accepting paths of Turing machines. This does not mean that VNP
0
=
#P; the former
is a collection of polynomial families whereas the latter is a collection of functions
from strings to whole numbers. But the complexity of evaluating polynomial families
in the former collection, at Boolean arguments, is closely related to what the latter
collection refers to. Koiran's proof actually shows the contrapositive: he first shows
that if VP
0
VNP
0
and P
2
ʲ
)
!
)
=
=
PSPACE, then the sequence
˄ ((
is polynomially
2
ʲ(
n
)
)
!
bounded in
ʲ
. So consider instead of each
n
!
the possibly larger factorial
(
,
where 2
ʲ(
n
)
−
1
2
ʲ(
n
)
. Then the sequence
2
ʲ(
n
)
)
!
)
<
n
∈
(
b
n
)
=
((
is easy to compute,
and each
b
n
is a multiple of
n
is ultimately easy to compute.
Since Perm
n
is not known to be complete for VNP
0
, what is? It turns out that
for several other VNP-complete families, the hardness proofs use no constants other
than
!
,so
(
n
!
)
1 and the membership proofs use circuits with small formal degree; hence
these families are complete for VNP
0
as well. As a concrete example, consider the
Hamilton cycle polynomial family HC
n
defined as follows: Let distinct variables
x
i
,
j
label the edges of the complete directed graph
D
n
.Let
C
n
denote the set of
all directed Hamiltonian cycles in
D
n
; elements of
C
n
can be described by cyclic
permutations
˃
∃
−
1
,
0
,
S
n
. Then
x
i
,˃(
i
)
HC
n
(
x
11
,...,
x
nn
)
=
˃
∃
C
n
This family is complete for VNP
0
;[
Mal03
].
Returning to the question “What does
VP
0
imply?”; Koiran [
Koi05
]
(
Perm
n
)
∃
2
n
ln 2
ₔ
∀
showed that it implies the sequence
is easy to compute. He also improved the
earlier-mentioned result in two ways, from “
VP
0
VNP
0
[
(
=
)
∧
(
=
)
]≡
P
PSPACE
VP
0
(
n
!
)
is ultimately easy to compute” to “
[
(
Perm
n
∃
)
∧
(
P
=
PSPACE
)
]≡
(
n
!
)
is easy to compute”.
Under the stronger hypothesis that VP
0
VNP
0
, we can showmore (again due to
=
(
2
n
i
1
2
i
2
2
2
n
2
2
n
[
Koi05
]). If VP
0
VNP
0
, then the sequences
−
1
=
)
,
ₔ
ln 2
∀
,
ₔ
ln 3
∀
,
=
2
2
n
ₔ
, all have polynomially bounded complexity, something that is not yet known
unconditionally.
ˀ
∀
Acknowledgments
I thank Arvind and Manindra for inviting me to contribute to this volume in
honour of Somenath Biswas, a wonderful professional colleague and friend. I thank CEFIPRA for
supporting an Indo-French collaboration (project 4702-1); many of my ideas for how to present
this survey were crystallised during my visit to University of Paris-Diderot during May-June 2012.
I have picked material I found interesting, and have not really attempted an exhaustive coverage.
I apologise in advance to thosewhose favourite results I have omitted. I gratefully acknowledgemany
insightful discussions with Eric Allender, V. Arvind, Hervé Fournier, Bruno Grenet, Nutan Limaye,
Guillaume Malod, Stefan Mengel, Sylvain Perifel, B. V. Raghavendra Rao, Nitin Saurabh, Karteek
Sreenivasaiah, Srikanth Srinivasan, V. Vinay. I thank the organisers of the Dagstuhl Seminars on
Circuits, Logic and Games (Feb 2010) and Computational Counting (Dec 2010) for inviting me
and giving me the opportunity to discuss these topics. The survey by Pascal Koiran at the Dagstuhl
seminar on Computational Counting in Dec 2010 was particularly helpful.
