论文标题
np $^{\＃p} $ = $ \存在$ pp和有关最大计数的其他评论
NP$^{\#P}$ = $\exists$PP and other remarks about maximized counting
论文作者
论文摘要
我们考虑以下决策问题DMAX＃SAT及其概括：给定无量化的命题公式$ f（\ MathBf {x}，\ Mathbf {y}）$，其中$ \ m athbf {x}}，\ m mathbf {y}是$ b $ $ b $ $ b $ $ b $ $ b $ $ \＃\ {\ Mathbf {y} \ mid f（\ Mathbf {X}，\ Mathbf {y}）\} \ geq b $。这是Max＃SAT问题的决策版：查找$ \ Mathbf {x} $和$ b $的最大$ b $。
We consider the following decision problem DMAX#SAT, and generalizations thereof: given a quantifier-free propositional formula $F(\mathbf{x},\mathbf{y})$, where $\mathbf{x},\mathbf{y}$ are tuples of variables, and a bound $B$, determine if there is $\vec{x}$ such that $\#\{\mathbf{y} \mid F(\mathbf{x},\mathbf{y})\} \geq B$. This is the decision version of the problem of MAX#SAT: finding $\mathbf{x}$ and $B$ for maximal $B$.
