Counting Complexity and Sharp-P: Examples and Counterexamples

The paths are start $\xrightarrow{0}$ accept-with-tag-$0$'' and start $\stackrel{1}{\to }$ accept-with-tag-$1$''. Padding repeats the final configuration, so these give two and only two legal accepting tableaux.

In the exact encoding of [L1], the tableau variables are uniquely fixed by one of these tableaux and every auxiliary variable is constrained by a biconditional with the subformula it names. Equivalently, after eliminating those uniquely determined variables, the formula is the tautology $b\vee \mathrm{\neg }b$ with declared variable $b$. Its two assignments correspond bijectively to the two paths.

Therefore the source accepting-path count and the formula's satisfying- assignment count are both exactly $2$.

The formula is equivalent to $y$: the assignments $(0,1)$ and $(1,1)$ satisfy it, while $(0,0)$ and $(1,0)$ do not. Thus [L1] gives $\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(\phi )=2$, returned as ${10}_2$.

Testing the returned integer against zero accepts, which is correct because the displayed satisfying assignments exist. The single exact query summarizes all four assignments.

This is the promised finite instance of the $\mathrm{N}\mathrm{P}\subseteq {\mathrm{P}}^{\mathrm{\#}\mathrm{P}}$ route.

Exactly three assignments satisfy $x\vee y$. Exactly the two assignments with unequal bits satisfy $(x\vee y)\wedge (\mathrm{\neg }x\vee \mathrm{\neg }y)$. Hence [L1] gives outputs $3$ and $2$, neither in the Boolean codomain $\{0,1\}$.

Both counts are positive, so the associated SAT predicate maps both inputs to yes. It therefore discards information that NumberSAT retains.

These explicit values show that NumberSAT is a numerical function, not a Boolean membership predicate.