Counting Complexity and Sharp-P

First check the formula syntax and declared-variable list deterministically; on malformed input reject without making a nondeterministic choice. On a valid input with $n$ declared variables, make exactly $n$ binary choices, interpret them in the declared order as an assignment, evaluate the formula, and accept exactly when it is true.

The $2^n$ computation paths are in bijection with the $2^n$ declared assignments, and a path accepts exactly when its assignment satisfies the formula. At $n=0$ there is one path, corresponding to the empty assignment; malformed input has no accepting path. Thus the accepting-path count is exactly $\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(\phi )$.

The machine runs in polynomial time, so its counting function belongs to $\mathrm{\#}\mathrm{P}$ by [L1].

Replace $N$ by a fixed one-tape simulator $N^{\ast }$. Encode the finitely many simulated tapes as delimiter-separated blocks with marked head cells. To simulate one step, make a deterministic sweep to collect the finitely many scanned symbols, choose exactly one transition of $N$ nondeterministically, record its transition tag in a distinct intermediate state, and make deterministic sweeps to update marked cells and shift blocks if a head enters a new blank cell. The finite transition table from [F1] makes all sweep-control states fixed. After $t$ simulated steps on an input of length $n$, at most $n+O(t)$ cells are represented, so each sweep costs $O(n+t)$ and the full simulation costs $O((n+t{)}^2)$; the tag step adds constant overhead. Even choices with the same eventual successor yield different tagged tableau rows. Erasing deterministic sweeps and reading tags is a bijection between accepting paths. Choose a polynomial $T(n)\ge n+1$ bounding the running time and every visited tape position on all bounded branches, then deterministically pad every halted branch to time $T(n)$. This supplies [L1]--[L3].

Use one-hot tableau variables for the symbol (including the tagged state) in every time-cell position. The initial-row, exactly-one-symbol, local-transition, and accepting constraints use only those variables. Take their conjunction as ${\phi }_{N,x}$ without introducing auxiliary variables. Let $V_{N,x}$ list every cell variable $X_{t,c,a}$ once, in lexicographic order of time, cell, and a fixed order on the simulator alphabet. Output the encoded pair $({\phi }_{N,x},V_{N,x})$, which is well formed for NumberSAT.

An accepting path fixes every cell of its padded tableau and therefore one truth value for every tableau variable. Every declared variable is such a cell variable, so none contributes a free choice. Conversely, any satisfying assignment gives exactly one legal accepting tableau by [L2], and the retained choice tags recover exactly one accepting path of $N^{\ast }$, hence exactly one accepting path of $N$ by step 1.1. These maps are inverse, so $\mathrm{\#}{\mathrm{acc}}_N(x)=\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}({\phi }_{N,x},V_{N,x})\mathrm{.}$

The tableau has polynomial dimensions, its local constraints have polynomial total size, and [L3] supplies the polynomial-time construction. Enumerating the polynomially many declared variable names in the specified order also takes polynomial time. Together with the exact equality in step 3.1, [L4] proves parsimony.

Choose a machine $N$ with $f(x)=\mathrm{\#}{\mathrm{acc}}_N(x)$ as supplied by [L1]. Apply [L3] to compute the formula $r(x)={\phi }_{N,x}$ in polynomial time.

For every input $x$, the bijection in [L3] gives the exact chain $f(x)=\mathrm{\#}{\mathrm{acc}}_N(x)=\mathrm{\#}\mathrm{sat}({\phi }_{N,x})=\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(r(x))\mathrm{.}$ Thus $r$ is a parsimonious reduction by [L4].

Since $f$ was arbitrary, step 2.1 proves $\mathrm{\#}\mathrm{P}$-hardness, and [L2] proves membership.

On input $x$, compute $m=f(x)$ using [L1] and let $k=\max (1,\mathrm{\mid }\mathrm{bin}(m)\mathrm{\mid })$. Make exactly $k$ binary nondeterministic choices, producing one path for every integer $u\in [0,2^k)$. Accept iff $u<m$.

Exactly the $m$ values $u=0,\dots ,m-1$ accept; all power-of-two padding values reject. This remains correct at $m=0$, when no path accepts. The output length and hence $k$ are polynomially bounded by the running time in [L1].

The constructed machine runs in polynomial time and has accepting-path count $f(x)$, so $f\in \mathrm{\#}\mathrm{P}$ by [L2].

For the sum, make one initial binary choice. On its $0$ branch simulate $M_f(x)$ and on its $1$ branch simulate $M_g(x)$. The accepting paths are a disjoint tagged union, so their number is $f(x)+g(x)$.

For the product, simulate $M_f(x)$; after each accepting path, independently simulate $M_g(x)$, while every rejecting $M_f$ path rejects. Each of the $f(x)$ accepting first-stage paths has exactly $g(x)$ accepting continuations, so the total is $f(x)g(x)$. This also covers either count being zero.

Both composite machines run in polynomial time, so [L1] puts their two counting functions in $\mathrm{\#}\mathrm{P}$.

Let a PP machine use exactly $p(\mathrm{\mid }x\mathrm{\mid })$ random bits, padding unused bits if necessary, and let $a(x)$ and $r(x)$ be its accepting and rejecting choice-string counts. Then $g=a-r$ is in GapP by [L1], and $g(x)>0$ exactly when $a(x)>2^{p(\mathrm{\mid }x\mathrm{\mid })-1}$, the strict PP condition in [L2].

Conversely take a GapP machine for $g$, let $f$ count its accepting paths, and let $h$ count its rejecting paths (the latter is a #P count after exchanging final labels), so $g=f-h$. Choose a common polynomial bound $p(\mathrm{\mid }x\mathrm{\mid })$ on the number of binary choices. Encode each original path by its actual choice bits followed by only zeroes to length $p$; reject a nonzero unused suffix. This gives exactly one full-length encoding per original path and does not multiply either count when a branch halts early. Each normalized machine has $2^p$ total full-length paths. Construct a machine with one leading choice: on branch $0$ run the machine for $f$ with its labels unchanged; on branch $1$ run the machine for $h$ with accept and reject exchanged. It has $f(x)+(2^p-h(x))$ accepting paths out of $2^{p+1}$, a strict majority exactly when $f(x)-h(x)>0$.

Steps 1.1 and 1.2 prove the two implications, including the strict zero boundary.

On a well-formed formula with $n$ declared variables, a probabilistic machine chooses the $n$ assignment bits uniformly and accepts exactly on a satisfying assignment. Its acceptance probability is $\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(\phi )\mathrm{/}{2}^n$, so [L1] gives membership in PP; for $n=0$ the unique random string is the empty assignment.

For hardness, normalize a PP machine to $2^p$ paths with $p\ge 1$, $a$ of them accepting. By [L3] obtain a formula $\phi$ with exactly $a$ satisfying assignments. Add uniquely forced variables until its declared count $q$ obeys $q\ge p$, preserving its count. For $u=(u_{q-1},\dots ,u_0)$ let $T(u)=u_{q-1}\vee \cdots \vee u_{p-1}$; exactly $2^q-2^{p-1}$ assignments satisfy $T$. With a fresh selector $z$, put $\theta =(\mathrm{\neg }z\wedge \phi )\vee (z\wedge T)\mathrm{.}$ Then $\mathrm{\#}\theta =a+2^q-2^{p-1}>2^q⟺a>2^{p-1}\mathrm{.}$ The formula and its declared list are produced in polynomial time.

Step 1.2 is a membership-preserving reduction from every PP language to MajoritySAT, and step 1.1 gives membership; hence MajoritySAT is PP-complete.

By [L2], choose $g\in \mathrm{G}\mathrm{a}\mathrm{p}\mathrm{P}$ with $L=\{x:g(x)>0\}$. Since $g$ is integer-valued, $x\mathrm{\notin }L⟺g(x)\le 0⟺1-g(x)>0.$

If $g$ is witnessed by a machine, exchanging its accepting and rejecting labels witnesses $-g$ in GapP. A deterministic accepting machine witnesses the constant-one gap, and a leading tagged branch adds two gap functions. Hence $1-g\in \mathrm{G}\mathrm{a}\mathrm{p}\mathrm{P}$ by [L1].

Applying [L2] to $1-g$ shows that $\bar{L}\in \mathrm{P}\mathrm{P}$. The added $1$ is exactly what turns the non-strict condition $g\le 0$ into strict positivity, including $g=0$.

Enlarge $p$ if needed to a nonnegative integer-valued polynomial bound, and put $m=p(\mathrm{\mid }x\mathrm{\mid })$. Define $h(x)=\mathrm{\mid }\{u\in \{0,1{\}}^{\ast }:\mathrm{\mid }u\mathrm{\mid }\le m,R(x,u)=1\}\mathrm{\mid }$. A binary-branching polynomial-time machine guesses a word $y$ of length $m+1$. It rejects if $y$ has no zero; otherwise it writes $y=1^{m-\mathrm{\mid }u\mathrm{\mid }}0u$ using the first zero, and accepts exactly when $R(x,u)=1$. This encoding is a bijection between words $u$ of length at most $m$ and guessed words $y$ with a zero. Thus the accepting-path count is exactly $h(x)$, so $h\in \mathrm{\#}\mathrm{P}$.

By [L3], compute in polynomial time a formula $r(x)$ with $h(x)=\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(r(x))$. A deterministic oracle machine queries $r(x)$ and accepts iff the returned binary integer is nonzero. Since $h(x)\le 2^{m+1}-1$, the answer has at most $m+1$ bits. By the verifier definition, $h(x)>0$ exactly when $x\in L$.

This oracle machine decides $L$, proving the containment.

By direct enumeration, $\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(\phi )=3$ and $\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(\psi )=2$. NumberSAT is a $\mathrm{\#}\mathrm{P}$ function, while neither $2$ nor $3$ is a Boolean membership value.

The associated decision language SAT retains only the predicate $\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(\theta )>0$; it answers yes on both displayed formulas and forgets their distinct counts.

Thus, under [L1], $\mathrm{\#}\mathrm{P}$ is a numerical function class rather than a language class.

Let $r(w)=w$ for every binary word $w$. This is a total linear-time map. The two positive-count decision languages are both $\{0,1{\}}^{\ast }$, so $r$ is a many-one reduction between them by [L1].

For every $w$, the source has exactly one accepting witness $\epsilon$, whereas the target has exactly the two accepting witnesses $0,1$. Hence $f(w)=1\mathrm{\ne }2=g(r(w))$, so $r$ is not parsimonious under [L2]. Both witness relations are decidable in constant time once their witness is read.

This one polynomial-time decision reduction refutes the universal claim.