1
$\begingroup$

Consider a problem such as weighted model counting for propositional logic. The problem of enumerating all models M of a logic formula f and summing their weights w(M) is #P. What happens if the weight is a function of the model and the task of computing the weight w(M) given M is in itself #P? Whats the complexity of the total problem?

$\endgroup$

1 Answer 1

2
$\begingroup$

The result is in #P. Suppose there are 50 states, and each state has 10 cities. Then how many cities are there in total?

Now suppose we have a polytime verifier for states: $S(x)$ outputs 1 iff $x$ is a state. We also have a polytime verifier for cities: $C(x,y)$ outputs 1 iff $y$ is a city in state $x$. Then counting the number of states is in #P: it's the number of $x$ such that $S(x)=1$. If you think a bit, you can see that counting the number of cities is also in #P: it's the number of pairs $(x,y)$ such that $S(x)=1 \land C(x,y)=1$. Can you come up with a polytime verifier $V$ such that $V(x,y)=1$ iff $x$ is a state and $y$ is a cities in that state? I bet you can. Consequently, counting the number of such pairs (i.e., counting the number of cities) is in #P.

Now apply the same idea to your problem, and you should be able to figure out the answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.