Information Technology Reference
In-Depth Information
VSAC
1
circuit
D
n
can be normalised to have alternating
×
nodes having fanin 2, and all leaves at the same depth. Choose
N
at least as large
as min
+
×
and
nodes, with all
2
depth
(
D
n
)
}
, and also at least as large as the number of variables
in
C
n
. Now, the computation of
D
n
can be embedded into
C
N
: Choose the right
number of
{
size
(
D
n
),
nodes at each even layer, and by carefully assigning 0,1 values to the
y
variables, ensure that they compute the required combinations of polynomials from
the previous even layer.
The circuits described above are called
universal circuits
in [
SY10
], because every
circuit is a projection of the universal circuit of appropriate size. And if we start with
VP circuits, the projections are
p
-projections.
So now we know that VP has complete families under
p
-projections as well. But
generic polynomials, universal circuits, and the polynomials they compute, are rather
artifical. Are there other families that are defined independent of circuits and are VP-
complete? Actually, we know very few. Recently, Stefan Mengel [
Men11
] made
further progress here, considering polynomial families associated with constraint
satisfaction problems CSPs. (This builds on earlier work by Briquel, Koiran, Meer
[
BK09
,
BKM11
], though they did not explicitly look for VP-completeness.) Let's
first review what CSPs are. Think of them as generalising CNF-SAT. In CNF-SAT,
each clause forbids one assignment to the variables in it. (e.g the clause
x
1
∩
+
x
3
forbids
x
1
=
1.) In a CSP, variables can take values from a larger domain,
not necessarily 0,1. Each constraint is like a clause; it has a set of variables, and
it forbids certain combinations of assignments to these variables. (e.g on domain
{
0
,
x
3
=
,
,
}
a constraint on
x
1
,
x
2
could say that
x
1
=
,
,
cc
are forbidden, the other 6 assignments satisfy this constraint.) As in SAT, we look for
assignments satisfying all constraints. If the domain has size 2, the CSP is Boolean.
If each constraint involves 2 (or less) variables, the CSP is binary. As usual, consider
not just a CSP but a family of CSPs
a
b
c
x
2
. That is, assignments
aa
bb
n
has domain
D
n
. For tractability,
we will require that the CSP is
p
-bounded; that is, the CSP has bounded arity (for
some fixed constant
c
, each constraint in every
(
n
)
, where
n
looks at no more than
c
variables),
and it has polynomial-sized domains (in
n
, the variables take values from a set
D
n
,
where the size of
D
n
is
p
-bounded). Now associate with each such CSP
(
n
)
a
polynomial family
(
Q
n
=
Q
(
n
))
, where
Q
n
is on the variable set
{
X
d
|
d
∃
D
n
}
and is defined as follows:
Q
(
n
)
=
D
n
[
a
satisfies
n
]
X
a
(
x
)
a
:
var
(
)
∗
x
∃
var
(
)
n
n
X
|
a
−
1
(
d
)
|
=
D
n
[
a
satisfies
n
]
d
a
:
var
(
n
)
∗
d
∃
D
n
(Recall,
is Boolean, 1 if and only if statement
S
is true.)Mengel has this wonderful
characterisation of the complexity of the family
[
S
]
. The characterisation involves
associating with the CSP a graph
G
; this graph has a vertex for each variable and an
edge between two variables if they occur simultaneously in some constraint. Now
the treewidth and pathwidth of the graph (these parameters describe roughly how
(
Q
n
)
