Information Technology Reference
In-Depth Information
tree-like or path-like the graph is, if we can consider blobs of vertices. The smaller the
blobs, the better the similarity. See [
Bod98
] for definitions and an overview.) relate
to the complexity. It also involves an assignment bound: a CSP is
c
-assignment-
bounded if for each constraint
˕
and each variable
x
in the constraint, the number
of distinct values possible for
x
in assignments satisfying
˕
is bounded by
c
,even
though the domain may be much larger. This seems like a strong condition, but recall
that Boolean CSPs are by definition 2-assignment-bounded.
Enough of definitions! Here's what Mengel shows:
1. For each
p
-bounded CSP
(
n
)
,
(
Q
(
n
))
is in VNP. Every family
(
f
n
)
in VNP
is a
p
-projection of
(
Q
(
n
))
for some
p
-bounded
(
n
)
.
2. For each
p
-bounded CSP
(
n
)
where
G
n
has bounded treewidth,
(
Q
(
n
))
is in
VP. Every family
(
f
n
)
in VP is a
p
-projection of
(
Q
(
n
))
for some
p
-bounded
where
G
is a tree (treewidth 1).
3. For each
p
-bounded CSP
binary
(
n
)
(
n
)
where
G
n
has bounded pathwidth,
(
Q
(
n
))
is in
VBP. Every family
(
f
n
)
inVBP is a
p
-projection of
(
Q
(
n
))
for some
p
-bounded
where
G
is a path (pathwidth 1).
4. For each
p
-bounded
c
-assignment-bounded CSP
binary
(
n
)
(
n
)
where
G
n
has bounded
treewidth,
(
Q
(
n
))
is inVF. Every family
(
f
n
)
inVF is a
p
-projection of
(
Q
(
n
))
for some
p
-bounded 2-assignment-bounded binary
(
n
)
where
G
has pathwidth
at most 26.
The hardness proofs involve looking at the structure of parse trees for VP, witnessing
paths for VBP.
Note that as stated, this falls slightly short of providing a single complete family
for VP. However, applying the hardness reduction from universal circuits will yield
a single CSP family that is VP-complete. To the best of my knowledge, this is the
first instance of a VP-hardness result for a family defined (almost) independent of
circuits.
All the above results require that the CSP has bounded arity. Unbounded arity
seems to immediately give rise to intractability. If arity is unconstrained, can other
types of restrictions still result in families in VP? For further progress in this direction,
see [
DM11
,
CDM13
].
4.6 Computing Integers
The questions concerning algebraic complexity classes are closely connected to
another very intriguing question. Let
N
>
1 be any natural number. Suppose we
want to build up
N
from 1, using only
+
,
−
and
×
. The most naive way of doing
this would be
N
1. But depending on
N
there can be many other
ways. Which is the
most efficient
way? That is, which way uses the least number of
+
=
1
+
1
+···+
at least once, and the
first time we use it we will generate 2. So let us not even count this mandatory
or
×
operations? To do anything non-trivial, we must use
+
+
.
How many more operations are needed?
