Counting Complexity and Sharp-P: Examples and Counterexamples

Use two distinct intermediate states $q_0^{\mathrm{\prime }}$ and $q_1^{\mathrm{\prime }}$ to record the first choice: from the initial state the machine branches to $q_b^{\mathrm{\prime }}$, then deterministically enters its single accepting state. These are its only two computation paths. Their first successor rows have different state tags, and padding repeats the final accepting configuration, so they give two and only two legal accepting tableaux.

In the exact encoding of [L1], every declared variable is a tableau cell variable and there are no auxiliary variables. Each of the two legal padded tableaux fixes every declared variable, and [L1] gives the converse from any satisfying assignment to exactly one accepting path. Hence the two paths correspond bijectively to the formula's satisfying assignments.

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.

By [L2], this is a finite instance of deciding satisfiability in ${\mathrm{P}}^{\mathrm{\#}\mathrm{P}}$ with one NumberSAT query.

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.