Computational Complexity: Complexity of Counting

Counting Problem

一些计数问题：

• $\sharp \text{CYCLE}$：计算有向图G中环的个数。
• $\sharp \text{SAT}$：使得该公式为真的真值指派的个数。

计数问题要远难于判定问题。

定理：如果$\sharp \text{CYCLE}$有多项式的算法，则$\textbf{P}=\textbf{NP}$。

$\sharp \textbf{P}$

对函数$f:\{0,1\} ^* \to \textbf{N}$，如果$\exists p : \textbf{N} \to \textbf{N}$和一个多项式图灵机$\mathbb{M}$使得$\forall x \in \{0,1\} ^*$，有：

$$
f(x)=|\{y \in \{0,1\} ^{p(|x|)}| \mathbb{M}(x,y)=1\}|
$$

其中，右边表示使得括号成立的$y$的个数。这样的$f$是在$\sharp \textbf{P}$中的。

上述定义可视为用“证据”定义的，因而也可用非确定图灵机定义$\sharp \textbf{P}$，此时$f$的值即为非确定图灵机回答YES的路径数。

$\textbf{PP}$可视为$\sharp \textbf{P}$的决策版本。

$\textbf{FP}$

函数$(f:\{0,1\} ^*\to \textbf{N}) \in \textbf{FP}$，如果该函数可由多项式图灵机计算。

$\textbf{FP} \subseteq \sharp\textbf{P}$

$\sharp \textbf{P}$完全

$f \in \sharp \textbf{P}\text{-complete}$如果$f \in \sharp \textbf{P}$且$\sharp \textbf{P} \in \textbf{FP} ^f$。

即$\sharp \textbf{P}$中的问题都可以通过调用$f$解决。

$\sharp \textbf{SAT}$是$\sharp \textbf{P}\text{-complete}$的。还是C-L归约。

$\sharp \textbf{SAT}$：$<\varphi, i>$，其中$\varphi$是可取范式，$i$是使得$\varphi$为真的真值指派的个数。

Valiant Theorem

Perm是$\sharp \textbf{P}$完全的。

Perm转换为有向图中包含所有结点的环。

把3CNF的变量和语句表示为图。

最终Perm=$4 ^{3m}\sharp \varphi$。

还要证明Perm$\le _K$0-1Perm：把边转为$k$条权为1的平行边。

Universal Hash Function

$\mathcal{H} \subseteq B ^A$，其中$B ^A$表示从$A$到$B$的函数。$\mathcal{H}$是通用哈希函数族，如果：

$$\text{Pr} _{h \in _R \mathcal{H}}[h(x)=h(x')]\le \frac{1}{|B|}$$

其中$x,x' \in A,x \ne x'$。

m-wise Independent Hash Function Family

$$
\text{Pr} _{h \in _R \mathcal{H} _{n,k}}[\land _{i=1} ^m h(x _i)= y _i]=\frac{1}{2 ^{mk}}
$$

则称$\mathcal{H} _{n,k}$是m-independent的。其中，$x _i$互不相等。$\mathcal{H} _{n,k}$将长度为$n$的串映射为长度为$k$的串。换句话说，$\mathcal{H} _{n,k}$能保证对$m$个串，其对每一位的映射都是独立的。

多项式线性方程的解，因为只有唯一解，所以能求出唯一的系数$a _0,...,a _{m-1}$。范德蒙德式。

Valiant-Vazirani Theorem

$\textbf{UP}$，对其中的类，非确定图灵机的所有路径中，至多有一条路径接受它。$\textbf{P}\subseteq \textbf{UP} \subseteq \textbf{NP}$。

$\textbf{USAT}$：只有唯一的真值指派使之为真。

定理：$\forall n$变量的$\phi$，存在多项式概率图灵机$\mathbb{A}$：

$$
\begin{align*}
&\phi \in \textbf{SAT} \to \text{Pr}[\mathbb{A}(\phi)\in \textbf{USAT}] \ge 1/(8n) \\
&\phi \notin \textbf{SAT} \to \text{Pr}[\mathbb{A}(\phi)\in \textbf{SAT}] =0
\end{align*}
$$

证明：对$\phi(x,y...,z)$，定义归约$\phi \land x=c _1 \land y= c _2\land...\land z = c _n$。由于$\phi$没有多项式算法，所以$c _1,...,c _n$是满足合取范式的猜测。

详细证明：集合并公式的拆分。
不能通过重复实验来提高概率，因为每次随机算法$\mathbb{A}$生成的都是随机的公式。

$\oplus \textbf{P}$

$\oplus\textbf{P}$，对其中的类，非确定图灵机的所有路径中，只有奇数条路径接受它（或者0条则表拒绝）。$\textbf{UP} \subseteq \oplus \textbf{P}$。

$\oplus \textbf{SAT}$是$\oplus \textbf{P}$完全的。

将前面的$\textbf{USAT}$换成$\oplus \textbf{SAT}$也是对的，且能重复实验提高精度，这就是Toda Theorem。

Toda Theorem：任何$\textbf{PH}$问题都能通过调用多项式次$\sharp \textbf{P}$完成，即：

$$
\textbf{PH} \subseteq \textbf{P} ^{\sharp \textbf{P}}
$$