Counting complexity

Counting complexity studies the computational resources needed to count solutions. For a polynomial time decidable binary relation $R$ and a polynomial $p$, a standard counting function isThe complexity class $\#\mathbf{P}$ consists of these functions, equivalently the numbers of accepting computations of Nondeterministic Turing machines running in polynomial time. The witness encoding matters: counting computation paths and counting distinct outputs can give different answers.

For the propositional formula $x\vee y$, the satisfying Boolean valuations are $01$, $10$ and $11$, so the answer is three. The associated decision problem asks only whether that count is positive. For a zero-one matrix, the permanent of a matrix counts perfect matchings in a bipartite graph. Testing whether any such perfect matching exists admits a polynomial-time algorithm, while counting them is $\#\mathbf{P}$-complete under polynomial-time Turing reductions.^[ref]

Valiant's permanent reduction encodes satisfying assignments as weighted cycle covers of a directed graph. The permanent of a matrix sums the products of edge weights over these cycle covers of a directed graph.

Variable tracks enforce consistent truth values, clause interchanges enforce satisfaction, and signed junctions cancel invalid boundary choices. The original construction giveswhere $t(F)$ is twice the number of literal occurrences minus the number of clauses. Arithmetic recovers the predictable factor. The correspondence is between assignments and weighted groups of covers, rather than individual covers. Further transformations yield zero-one matrices.^[ref]

The Variable gadget in Valiant's permanent reduction is a track with two coherent routing choices. Each takes one side's literal junctions; clause tracks must take the other side. Interpret the global choice as a truth value, making all occurrences consistent.^[ref]

The Clause gadget in Valiant's permanent reduction is an interchange that can take every proper subset of its literal junctions, uniquely, but cannot take all. Variable tracks must therefore take at least one junction, representing a true literal. An unsatisfied clause has no good route.^[ref]

The Exclusive-or gadget in Valiant's permanent reduction cancels invalid cycle covers of a directed graph using signed edge weights. In the original four-vertex junction matrix $X$, only vertices one and four have external connections. Writing $X(R;C)$ for row and column deletions, its permanents satisfyandSurviving weighted routes therefore enter once and leave at the opposite port. Invalid patterns have total weight zero, even when individual covers exist.^[ref]

A binary path-counting gadget constructs a directed acyclic graph with exactly $w$ directed paths from entrance $s$ to exit $t$, using $O(\log (w+1))$ vertices for a nonnegative integer $w$.

For $w>0$, read its binary expansion after the leading one. Begin with one edge $s\to v$. For each following bit $b$, add fresh vertices $u_0,u_1,v^{\prime }$ and edges $v\to u_0$, $v\to u_1$, $u_0\to v^{\prime }$, $u_1\to v^{\prime }$. If $b=1$, also add $s\to v^{\prime }$. Replace $v$ by $v^{\prime }$. The path count changes from $q$ to $2q+b$. Finally add $v\to t$. For $w=5$, the bits $101$ give counts $1,2,5$. For $w=0$, leave $s,t$ disconnected.

To replace a weighted edge $x\to y$ inside a cycle cover of a directed graph, identify $s=x,t=y$ and give each fresh internal vertex a unit-weight self-loop. If the replacement is unused, all fresh vertices use their self-loops, in one way. If it is used, the selected internal edges form one $x$-to-$y$ path, giving $w$ possibilities; all unused vertices use their self-loops. The internal graph is acyclic apart from these self-loops, so there are no other internal directed cycles. Thus the substitution preserves the weighted permanent of a matrix.

Balanced number 3-SAT is the counting version of 3-SAT under a promise that every variable has equally many positive and negative occurrences.