NP^#P = ∃PP and other remarks about maximized counting
share
We consider the following decision problem DMAX#SAT, and generalizations thereof: given a quantifier-free propositional formula F(𝐱,𝐲), where 𝐱,𝐲 are tuples of variables, and a bound B, determine if there is x⃗ such that #{𝐲| F(𝐱,𝐲)}≥ B. This is the decision version of the problem of MAX#SAT: finding 𝐱 and B for maximal B.
READ FULL TEXT