Information Technology Reference
In-Depth Information
made the size bounds in the conversions even more precise. So now we can say
VBP
VP w s , where the subscript w s stands for weakly skew.
(Note: Neither [ Tod92 ] not [ MP08 , Mal03 ] actually claimed linear size blow-up.
However, their constructions from weakly skew circuits to ABPs, with the standard
conversion from ABPs to skew circuits, does give linear blow-up. As far as I can see,
linear blow-up for weakly skew to skew circuits was explicitly observed in [ KK08 ,
Jan08 , Gre12a ].)
Taking this idea further, Malod and Portier provide a brilliant characterization
of the class VP. Say that a circuit is disjoint if at every node = ʲ ʳ , where
=
VP skew =
, the sub-circuits rooted at ʲ and ʳ are disjoint. This is just a
fancy (convoluted?) way of saying that the circuit is a formula. But now relax this
constraint a bit. Say that a circuit is multiplicatively disjoint or MD if at every
could be
+
or
×
node
= ʲ × ʳ , the sub-circuits rooted at ʲ and ʳ are disjoint. No restrictions apply to
×
+
nodes. Like formulas, MD circuits of size s have complete formal degree bounded
by s . But the MD restriction seems to allow more computation than formulas; for
instance, weakly skew circuits are MD, and so MD circuits can compute
in
polynomial size. Malod and Portier showed that in fact polynomial size MD circuits
can compute everything in VP, but nothing more. That is, VP
(
Det n )
VP MD . While this
fact can also be deduced once we have depth reduction to VSAC 1 , Malod and Portier
give a completely self-contained combinatorial proof which is very neat. Basically,
imagine that each node in the VP circuit is labelled with its formal degree. Now
make multiple copies of each node, inversely proportional to the formal degree. By
carefully deciding which copies of its children to use to construct a copy of a node,
multiplicative disjointness can be achieved with only polynomial blow-up in size.
A nice consequence of this characterisation of VP is a simpler proof of the fact that
VP is contained in ·
=
VF. The key observation used is that a circuit ismultiplicatively
disjoint exactly when every proof tree is already a subgraph of the circuit (even
without any unfolding into a formula). See [ MP08 ] for details.
Before wemove on, we note another surprising relation betweenABPs and formu-
las: VF equals the class of p -families computed by polynomial-size ABPs of constant
width. What is this resource “width”? Recall that an ABP is a DAG with edges going
“in the direction from s to t ”. Suppose we impose a layering constraint. The nodes of
the DAG must be laid out at the vertices of a rectangular w × ʲ
grid, the node s must
be at position
(
S
,
1
)
for some S
∃[ w ]
, the node t must be at position
(
T
,ʲ)
for some
T
∃[ w ]
, and edges can only go across one layer, from
(
i
,
k
)
to
(
j
,
k
+
1
)
for some
i
. Of course, any ABP can be converted to one of this form: just
sub-divide edges when necessary and label the sub-division path so that its weight
is the original edge's label (use lots of 1s). Now we say that w is the width of the
layered ABP and
,
j
∃[ w ]
, k
∃[ ʲ
1
]
B n )
is one where for some absolute constant c , each B n has width at most c . Seems quite
a squeeze - if we view moving from s towards t as an incremental computation, then
at each stage we can carry forward just c intermediate polynomials. We shouldn't
be able to do much this way, right? Wrong! Ben-Or and Cleve [ BOC92 ] showed, in
a proof cleverly extending Barrington's famous characterisation [ Bar89 ]ofNC 1 by
Boolean bounded-with branching programs, that every formula of depth D has an
ʲ
is the length. A bounded-width branching program family
(
Search WWH ::




Custom Search