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 }$. Between two transitions of $N$, the simulator's sweeps are deterministic; at an original nondeterministic transition it makes exactly the same tagged choice as $N$. Each such choice first enters a distinct intermediate state labelled by its transition tag, before deterministically executing that transition; these states are part of the recorded configuration. Even choices with the same eventual successor therefore give different tableau rows. Erasing the deterministic simulation steps and reading these tags is a bijection between accepting paths. The standard multitape-to-one-tape simulation has polynomial slowdown. Choose a polynomial $T(n)\ge n+1$ bounding both its running time and every tape position it can visit, and pad every halted branch to time $T(n)$. This supplies all hypotheses of [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 write $g=f-h$ with $f,h\in \mathrm{\#}\mathrm{P}$. Normalize their machines to guess the same $p(\mathrm{\mid }x\mathrm{\mid })$-bit string, rejecting invalid encodings, so each has exactly $2^p$ total 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$.

Define $h(x)=\mathrm{\mid }\{y\in \{0,1{\}}^{p(\mathrm{\mid }x\mathrm{\mid })}:R(x,y)=1\}\mathrm{\mid }$. A nondeterministic machine guesses the $p(\mathrm{\mid }x\mathrm{\mid })$ bits and accepts exactly when $R$ does, so $h\in \mathrm{\#}\mathrm{P}$ by [L2].

A deterministic polynomial-time oracle machine makes the single query $h(x)$ and accepts iff the returned binary integer is nonzero. The answer has at most $p(\mathrm{\mid }x\mathrm{\mid })+1$ bits, and $h(x)>0$ exactly when an NP witness exists.

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.

Define $r(\theta )=\theta \wedge (y\vee \mathrm{\neg }y)$ and declare $y$ in addition to the original variables. The map is polynomial time, and $\theta$ is satisfiable iff $r(\theta )$ is satisfiable, so it is a SAT-to-SAT many-one reduction by [L1].

Each satisfying assignment of $\theta$ has exactly two extensions, one for each value of $y$. Hence [L3] gives $\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(r(\theta ))=2\mathrm{N}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{A}\mathrm{T}(\theta )$. For the concrete input $\theta =x_1$, the counts are $1$ and $2$, so the map is not parsimonious under [L2].

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