Database Reference
In-Depth Information
A
Positive, Partitioned 2-CNF
propositional formula is a DNF formula of the form:
=
(X
i
∨
Y
j
)
(i,j)
∈
E
The #PP2CNF problem is “given a PP2CNF formula
, compute #
”.
Then, both #PP2DNF and #PP2CNF are hard for #P.
Provan and Ball
[
1983
] proved hardness for #PP2CNF; the result for #PP2DNF follows
immediately, because, if
and
are defined by the same set
E
, then #
2
n
=
−
#
, where
n
is
the total number of variables (both
X
i
and
Y
j
).
Returning to the probability computation problem, it is clear that this problem is hard for
#P, but it is technically not in #P, because it is not a counting problem. To explain its relationship
with #P, we start by assuming that the probability of every Boolean variable
X
i
is a rational number,
P(X
i
)
=
m
i
/n
i
.If
N
=
i
n
i
the product of all denominators, then
N
·
P ()
is an integer number.
Then, one can check that the problem “given inputs
and
P(X
i
)
=
m
i
/n
i
for
i
=
1
,
2
,...
, compute
N
P ()
” is in #P (details are given by
Dalvi and Suciu
[
2007c
]). Thus, while computing
P ()
is
not in #P, computing
N
·
P ()
is in #P.
Finally, we note that the probability computation problem can be strictly harder than the model
counting problem: more precisely, there exists families of propositional formulas
for which the
model counting problem is easy, yet the probability computation problem is hard. Indeed, consider
the following family of formulas:
·
n
=
X
i
Z
ij
Y
j
i,j
=
1
,n
The probability computation problem is hard, by a reduction from the PP2DNF problem: given a
PP2DNF formula
, define
P(Z
ij
)
=
0. Then
P ()
=
P(
n
)
. On the other hand, the reader can check, using standard combinatorics
arguments
1
, that the number of models of
n
is given by:
=
1 if the minterm
X
i
Y
j
occurs in
, otherwise define
P(Z
ij
)
n
k
n
l
(
2
n
2
2
n
2
−
kl
)
#
n
=
−
k
=
0
,n
l
=
0
,n
This is clearly computable in polynomial time.
1
Fix an assignment
θ
of the variables
X
1
,...,X
n
and
Y
1
,...,Y
n
. Suppose
k
of the
X
i
's are 1, and
l
of the
Y
j
's are 1. There are
2
n
2
possible assignments to the remaining variables
Z
ij
. An assignment that does
not
make
n
true is one that sets
Z
ij
=
0
=
1: there are 2
n
2
kl
such assignments. Their difference 2
n
2
−
2
n
2
−
−
kl
is the number of
for each
i, j
such that
X
i
=
1 and
Y
j
assignments to the
Z
-variables that make the formula true.
