08 计数复杂性

离散概率本质是计数问题。所以如果想要进一步研究由概率图灵机定义的复杂性类（比如$\text{PP}$），一个很自然的角度是研究计数问题的复杂性类。

到目前为止，我们讨论的都是判定问题。判定问题的输出只能是$0$或$1$，也就是说判定问题可以看作一类特殊的计数问题。然而直观上就可以接受，计数问题的难度可能远超判定问题的难度。下面我们通过有向图的简单环计数问题为例来说明这一点。

有向图的简单环计数($\sharp\texttt{CYCLE}$)

有向图上一个不包含重复点的环称为简单环（simple cycle，这里不考虑自环）。有向图的简单环判定问题是多项式可解的（比如，我们只需要在DFS的过程中记录时间戳就可以求解强连通分量，从而通过强连通分量的大小判定是否存在简单环），然而有向图的简单环计数问题($\sharp\texttt{CYCLE}$)是难的。我们证明，假设有向图的简单环计数问题($\sharp\texttt{CYCLE}$)有多项式图灵机可解，那么$\text{P}=\text{NP}$。

关键的观察是，哈密顿回路判定问题（一个$\text{NP}$-complete问题）可以归约到$\sharp\texttt{CYCLE}$。对于一个给定的有向图$G$，我们可以构造有向图$G'$，其中对$G$的每条边$u\to v$做拆分使得单看$u\to v$恰好有$2^m$条不同路径（交叉构造，此过程是多项式的）。取$m=n\log n$，我们可以做如下分析：如果$G$存在哈密顿回路，那么$G'$上简单环的个数至少为$(2^m)^n=2^{n^2\log n}=n^{n^2}$；如果$G$不存在哈密顿回路，那么$G$上简单环的个数至多$n^{n-1}$个，所以$G'$上简单环的个数至多$n^{n-1}\cdot (2^m)^{n-1}=n^{n^2-1}$个。所以如果调用多项式的$\sharp\texttt{CYCLE}$计数程序统计$G'$上简单环的个数，就可以通过环的个数是否超过$n^{n^2}$判定$G$上是否存在哈密顿回路，整个过程是多项式的。那么我们就可以多项式解决$\text{NP}$-complete问题，所以$\text{P}=\text{NP}$。

计数复杂性类

$\text{FP}$与$\sharp\text{P}$

多项式时间可解的计数问题类可以用确定性图灵机定义，记为$\text{FP}$（函数多项式时间复杂性类，Function Polynomial time complexity class）。具体的，如果存在一个确定性图灵机计算函数$f:\{0,1\}^*\to \N$，就令$f\in \text{FP}$。

容易发现，如果我们承认$\text{P}\neq \text{NP}$，那么上一节中提到的$\sharp\texttt{CYCLE}$并不在$\text{FP}$内。我们关心这样的计数问题，尽管它本身不是多项式可解的，但是它的解都是多项式可验证的。这类问题也应当构成一个复杂性类，这个类和$\text{FP}$的关系就好像$\text{NP}$和$\text{P}$的关系一样。我们把这个类称为$\sharp\text{P}$。和$\text{NP}$类一样，这个复杂性类可以用确定性图灵机定义，也可以用非确定性图灵机定义。用确定性图灵机定义：$f\in \sharp\text{P}$当且仅当存在确定性图灵机$\mathbb{M}$满足$f(x)=|\{y\in \{0,1\}^{p(|x|)}\mid \mathbb{M}(x,y)=1\}|$，这里的$y$相当于一个用来验证的解；用非确定性图灵机定义：如果存在非确定性图灵机$\N$判定某个$L\in \text{NP}$，并且在$\N$上输入$x$时（多项式时间内）恰好有$f(x)$条路径停机输出$1$，就称函数$f\in \sharp\text{P}$。

自然地，有$\text{FP}\subseteq \sharp\text{P}$，并且$\sharp\text{P}=\text{FP}\implies \text{NP}=\text{P}$。因为判定问题是一类特殊的计数问题，如果$\sharp \text{P}\subseteq \text{FP}$，也即一切非确定性图灵机多项式可计算的计数问题都存在确定性图灵机在多项式时间计算，那么一切非确定性图灵机多项式可判定的判定问题都存在确定性图灵机在多项式时间内判定，因此$\text{NP}\subseteq \text{P}$，所以$\text{NP}=\text{P}$。

还可以证明，$\text{P}=\text{PSPACE}\implies \sharp\text{P}=\text{FP}$。对于任何$f\in \sharp\text{P}$，我们要证明$f\in \text{FP}$。因为$f\in \sharp\text{P}$，存在一台确定性图灵机$\mathbb{M}$使得$f(x)=|\{y\in\{0,1\}^{p(|x|)}\mid \mathbb{M}(x,y)=1\}|$。于是我们可以构造一台确定性图灵机枚举$y$，这样就能以多项式空间求出$f(x)$。具体的，由于$\text{PSPACE}$是定义在判定问题上的，我们可以构造一系列$\text{PSPACE}$的图灵机用来判定$f(x)$的各个二进制位是否为$1$。既然$\text{P}=\text{PSPACE}$，这一系列图灵机都是$\text{P}$的。因此计算$f(x)$的图灵机自然是$\text{FP}$的。

注意到，$\text{PP}$类可以看作$\sharp\text{P}$类的判定版本，后者是数满足某一性质的解的个数，前者是判定满足某一性质的解是否超过一半。那么如果$\text{FP}=\sharp\text{P}$，也即如果计数是多项式时间的，那么$\text{PP}$也一定是多项式时间的。所以$\text{FP}=\sharp\text{P}\implies \text{P}=\text{PP}$。能不能反过来证明，$\text{PP}=\text{P}\implies \text{FP}=\sharp\text{P}$也成立呢？也就是证明$\text{PP}=\text{P}\implies \sharp\text{P}\subseteq \text{FP}$呢？答案是肯定的。这里的核心观察是，我们可以用二分法把计数问题转化为判定问题，二分的次数是多项式次（因为总数是指数的），而如果判定过程有多项式算法，那么整个二分也就是多项式算法了。具体证明如下：Pf. 设$f\in \sharp\text{P}$，那么根据定义存在确定性图灵机$\mathbb{M}$满足$f(x)=|\{y\in \{0,1\}^{p(|x|)}\mid \mathbb{M}(x,y)=1\}|$。基于$\mathbb{M}$，我们可以任取一$\ell\in\{0,1\}^{p(|x|)}$，定义一个图灵机$\mathbb{M}_\ell$，它接受输入$x$和一个$|p(x)|+1$位的二进制串$b\|y$，若$b=1$则$\mathbb{M}_\ell(x,b\|y)=\mathbb{M}(x,y)$，若$b=0$则$\mathbb{M}_\ell(x,b\|y)=\mathbb{1}[y<\ell]$。把$b\| y$看作随机串，$\mathbb{M}_\ell$就对应着一台接受输入$x$的概率图灵机$\mathbb{P}_\ell$，$\mathbb{P}_\ell(x)=1$当且仅当$f(x)+\ell>\dfrac{2^{p(|x|)+1}}{2}=2^{p(|x|)}$。设$\mathbb{P}_\ell$判定预言$L$，则$L\in\text{PP}$。由前提$\text{PP}=\text{P}$，$L\in\text{P}$。所以，$\forall \ell\in\{0,1\}^{p(|x|)}$，我们能够多项式时间判定是否成立$f(x)>2^{p(|x|)}-\ell$。注意到$2^{p(|x|)}-\ell$的取值范围恰好也是$\{0,1\}^{p(|x|)}$，所以我们可以在整个值域上二分。Qed. 所以最终我们得到$\text{PP}=\text{P}\iff \text{FP}=\sharp\text{P}$。

$\sharp\text{P}$-completeness

一个自然的问题是，如何定义$\sharp\text{P}$中最难的问题？也就是问，如何定义计数问题之间的（多项式）归约？我们依然可以通过oracle来定义：函数$f$能多项式归约到$g$的含义是，通过带有oracle $g$的确定性图灵机计算多项式时间能够计算$f$。也即$f\in \text{FP}^g$。由此，$f$是$\sharp\text{P}$-hard问题当且仅当$\forall g\in \sharp\text{P}$，$g \in \text{FP}^f$。如果进一步满足$f\in\sharp\text{P}$，则称$f$是$\sharp\text{P}$-complete问题。

$\sharp\texttt{SAT}$问题是$\sharp\text{P}$-complete的。顾名思义，$\sharp\texttt{SAT}$问题中这样一个函数，输入一个CNF（对应的二进制串），输出满足这个CNF的可满足赋值个数。（和证明$\texttt{SAT}$是$\text{NP}$-complete的过程很相似）

01矩阵的permanant（积和式）计算是$\sharp\text{P}$-complete的。这是为Valiant定理。矩阵$A$的permanant定义为$\texttt{perm}(A)=\sum\limits_{\sigma\in P_n}\prod\limits_{i=1}^n A_{i,\sigma(i)}$。注意到矩阵的行列式定义为$\det(A)=\sum\limits_{\sigma\in P_n}(-1)^{sw(\sigma)}\prod\limits_{i=1}^n A_{i,\sigma(i)}$ $,sw(\sigma)$表示permutation $\sigma$的逆序对个数。行列式可以在高斯消元的过程中顺带算出，因此由多项式时间算法。而Valiant定理告诉我们，作为计数问题的permanant问题尽管和行列式相比只差了一个逆序对的系数，却没有多项式时间算法（在$\text{P}\neq\text{NP}$的假设下）。

同样用二分法把计数问题转化为判定问题的思想，可以证明$\text{P}^\text{PP}=\text{P}^{\sharp\text{P}}$。这意味着$\text{PP}$和$\sharp\text{P}$在作为oracle的复杂性类意义下是等价的。因为$\natural \texttt{SAT}$是$\text{PP}$-complete的，$\sharp\texttt{SAT}$是$\sharp\text{P}$-complete的，因此只需证明$\text{P}^{\natural \texttt{SAT}}=\text{P}^{\sharp\texttt{SAT}}$。下证$\text{P}^{\natural \texttt{SAT}}\subseteq \text{P}^{\sharp\texttt{SAT}}$：$\forall L\in \text{P}^{\natural \texttt{SAT}}$，设图灵机$\mathbb{M}^{\natural\texttt{SAT}}$判定$L$，我们可以基于此设计$\mathbb{M}^{\sharp\texttt{SAT}}$，在前者调用$\natural\texttt{SAT}$ oracle时，我们只需调用$\sharp\texttt{SAT}$判断结果是否超过总赋值个数的一半，也可以得到相同的结果，因此$L\in\text{P}^{\sharp \texttt{SAT}}$。下证$\text{P}^{\sharp\texttt{SAT}}\subseteq \text{P}^{\natural \texttt{SAT}}$：$\forall L\in \text{P}^{\sharp \texttt{SAT}}$，判定$L$的图灵机$\mathbb{M}$至多调用多项式次$\sharp\texttt{SAT}$ oracle，对于每一次调用我们只需用$\natural\texttt{SAT}$二分也可以得到相同的结果，而二分的次数是多项式次的，因此$L\in\text{P}^{\natural \texttt{SAT}}$。