holant problem

• 1. 定义
• 2. 结论
• proof

1. 定义

• signature(local constraint function): A map $f:A\to B$ is a signature if (($\exists n\in \mathbb{N},q\in {\mathbb{Z}}^{+}$ s.t. $A=[q{]}^n$) and ($\exists$ a commutative semiring $R$ s.t. $B=R$)). The set of signatures is denoted by $\mathcal{F}$
• symmetric signature: A signature $f:[q{]}^n\to R$ is symmetric if $f$ is invariant under permutation of the variables
• signature grid: A signature grid $\Omega =(G,\pi )$ over $\mathcal{F}$ consists of a graph $G=(V,E)$ and a mapping $\pi$ that assigns to each vertex $v\in V$ an $f_v\in \mathcal{F}$ and a linear order(total order) of the incident edges at $v$.The arity of $f$ is equal to the degree at $v$, and the incident edges at $v$ are associated with the input variables of $f_v$.
• planar signature grid: A planar signature grid is a signature grid such that its underlying graph is planar and for some planar embedding, for every vertex $v$, the linear order of the incident edges at $v$ agrees with the clockwise cyclic order of the incident edges at $v$ in the embedding starting with some particular edge.
• bipartite signature grid: For signature sets $F$ and $G$, a bipartite signature grid over $(F|G)$ is a signature grid $\Omega =(H,\pi )$ over $F\cup G$, where $H=(V,E)$ is a bipartite graph with bipartition $V=(V_1,V_2)$ such that $\pi (V_1)\subseteq F$ and $\pi (V_2)\subseteq G$.
• Holant problem $Holan{t}_q(\mathcal{F})$:
  • input: A signature grid $\Omega =(G=(V,E),\pi )$ over $\mathcal{F}$
  • output: $Holan{t}_q(\Omega ;\mathcal{F})={\sum }_{\sigma :E\to [q]}{\prod }_{v\in V}{f}_v(\sigma {|}_{E(v)})$, where $E(v)$ is the set of edges incident to $v$
• tractable: polynomial-time computable
• p is the set of functions $f:\{0,1{\}}^{\ast }\to \mathbb{N}$ such that there exists a polynomial $p:\mathbb{N}\to \mathbb{N}$ and a polynomial-time deterministic Turing machine $V$, called the verifier, such that for every $x\in \{0,1{\}}^{\ast }$, $f(x)=|\{y\in \{0,1{\}}^{p(|x|)}:V(x,y)=1\}|$ (In other words, $f(x)$ equals the size of the set containing all of the polynomial-size certificates).

2. 结论

• $CS{P}_q^d(\mathcal{F}){\equiv }_{T}Holan{t}_q({\mathcal{EQ}}_d|\mathcal{F})=Holan{t}_q({\mathcal{EQ}}_d\cup \mathcal{F})$

• Let $\mathcal{F}$ be a set of signatures over a domain of size $q$. If there exists an $\mathcal{F}$-gate with signature $f$, then ${\text{Holant}}_q(\mathcal{F},f){\le }_T{\text{Holant}}_q(\mathcal{F})$.

• Let $\mathcal{F}$ and $\mathcal{G}$ be sets of complex-valued signatures over a domain of size $q$. Suppose $\Omega$ is a bipartite signature grid over $(\mathcal{F}\mid \mathcal{G})$. If $T\in {\text{GL}}_q(\mathbb{C})$, then ${\text{Holant}}_q(\Omega ;\mathcal{F}\mid \mathcal{G})={\text{Holant}}_q({\Omega }^{\prime };\mathcal{F}T\mid T^{-1}\mathcal{G}),$ where ${\Omega }^{\prime }$ is the corresponding signature grid over $(\mathcal{F}T\mid T^{-1}\mathcal{G})$.

proof

记号与基变换

设 $G=(U,V,E)$ 是有限无向二分图。对每个顶点 $w\in U\cup V$，固定关联边集 $E(w)$ 的一个次序，并记 $d_w=|E(w)|$。左、右两侧顶点分别赋予复值签名

$$f_u:[q{]}^{d_u}\to \mathbb{C}(u\in U),g_v:[q{]}^{d_v}\to \mathbb{C}(v\in V).$$

若 $\sigma :E\to [q]$ 是边赋值，则 $\sigma {|}_{E(w)}$ 表示按照上述固定次序排列的局部赋值元组。对应的 Holant 值为

$${\mathrm{Holant}}_q(G;\mathcal{F}\mid \mathcal{G})=\sum _{\sigma \in [q{]}^E}\prod _{u\in U}{f}_u\left(\sigma {|}_{E(u)}\right)\prod _{v\in V}{g}_v\left(\sigma {|}_{E(v)}\right),$$

其中 $\mathcal{F}=\{f_u{\}}_{u\in U}$，$\mathcal{G}=\{g_v{\}}_{v\in V}$。

取任意 $T\in {\mathrm{GL}}_q(\mathbb{C})$。对 $u\in U$，定义 $f_u^{\prime }=f_u{T}^{\otimes d_u}$，即

$$f_u^{\prime }(x_1,\dots ,x_{d_u})=\sum _{y_1,\dots ,y_{d_u}\in [q]}{f}_u(y_1,\dots ,y_{d_u})\prod _{i=1}^{d_u}{T}_{y_i,x_i}.$$

对 $v\in V$，定义 $g_v^{\prime }=(T^{-1}{)}^{\otimes d_v}{g}_v$，即

$$g_v^{\prime }(x_1,\dots ,x_{d_v})=\sum _{z_1,\dots ,z_{d_v}\in [q]}{g}_v(z_1,\dots ,z_{d_v})\prod _{j=1}^{d_v}(T^{-1}{)}_{x_j,z_j}.$$

分别记 $\mathcal{F}T=\{f_u^{\prime }{\}}_{u\in U}$ 和
$T^{-1}\mathcal{G}=\{g_v^{\prime }{\}}_{v\in V}$。左右两侧采用相反的变换方向，正是为了使每条边上的 $T$ 与 $T^{-1}$ 在张量收缩时相消。

定理

Valiant 全息变换定理（二分 Holant 形式）。 对任意上述二分签名网格和任意 $T\in {\mathrm{GL}}_q(\mathbb{C})$，都有

$${\mathrm{Holant}}_q(G;\mathcal{F}\mid \mathcal{G})={\mathrm{Holant}}_q(G;\mathcal{F}T\mid T^{-1}\mathcal{G}).$$

证明

记

$$Z^{\prime }={\mathrm{Holant}}_q(G;\mathcal{F}T\mid T^{-1}\mathcal{G}).$$

对任意变换后的边赋值 ${\sigma }^{\prime }\in [q{]}^E$，将各顶点内部的求和变量分别拼接为全局赋值 $\sigma ,\tau \in [q{]}^E$，可得

$$\prod _{u\in U}{f}_u^{\prime }\left({\sigma }^{\prime }{|}_{E(u)}\right)=\sum _{\sigma \in [q{]}^E}\left(\prod _{u\in U}{f}_u\left(\sigma {|}_{E(u)}\right)\right)\left(\prod _{e\in E}{T}_{\sigma (e),{\sigma }^{\prime }(e)}\right),$$

以及

$$\prod _{v\in V}{g}_v^{\prime }\left({\sigma }^{\prime }{|}_{E(v)}\right)=\sum _{\tau \in [q{]}^E}\left(\prod _{v\in V}{g}_v\left(\tau {|}_{E(v)}\right)\right)\left(\prod _{e\in E}(T^{-1}{)}_{{\sigma }^{\prime }(e),\tau (e)}\right).$$

将二式代入 $Z^{\prime }$。由于所有集合均有限，可以交换求和次序，于是

$$\begin{array}{rl}{Z}^{\prime }& =\sum _{\sigma \in [q{]}^E}\sum _{\tau \in [q{]}^E}\left(\prod _{u\in U}{f}_u\left(\sigma {|}_{E(u)}\right)\right)\left(\prod _{v\in V}{g}_v\left(\tau {|}_{E(v)}\right)\right)\\ & \cdot \sum _{{\sigma }^{\prime }\in [q{]}^E}\prod _{e\in E}{T}_{\sigma (e),{\sigma }^{\prime }(e)}(T^{-1}{)}_{{\sigma }^{\prime }(e),\tau (e)}.\end{array}$$

内层被积项在不同边之间没有共享变量，而 $[q{]}^E$ 是各边状态空间的笛卡尔积，因此

$$\begin{array}{rl}& \sum _{{\sigma }^{\prime }\in [q{]}^E}\prod _{e\in E}{T}_{\sigma (e),{\sigma }^{\prime }(e)}(T^{-1}{)}_{{\sigma }^{\prime }(e),\tau (e)}\\ & =\prod _{e\in E}\sum _{k\in [q]}{T}_{\sigma (e),k}(T^{-1}{)}_{k,\tau (e)}\\ & =\prod _{e\in E}(T{T}^{-1}{)}_{\sigma (e),\tau (e)}=\prod _{e\in E}{\delta }_{\sigma (e),\tau (e)},\end{array}$$

其中 $\delta$ 是 Kronecker delta。最后一个乘积当且仅当 $\sigma =\tau$ 时等于 $1$，否则等于 $0$。所以对 $\tau$ 的求和坍缩为唯一可能的赋值 $\tau =\sigma$：

$$\begin{array}{rl}{Z}^{\prime }& =\sum _{\sigma \in [q{]}^E}\prod _{u\in U}{f}_u\left(\sigma {|}_{E(u)}\right)\prod _{v\in V}{g}_v\left(\sigma {|}_{E(v)}\right)\\ & ={\mathrm{Holant}}_q(G;\mathcal{F}\mid \mathcal{G}).\end{array}$$

故定理成立。

因子化恒等式

下面详细说明证明中的按边因子化。设

$$E=\{e_1,e_2,\dots ,e_m\},m=|E|,$$

并定义

$$A(e,k)=T_{\sigma (e),k}(T^{-1}{)}_{k,\tau (e)}.$$

全局赋值 ${\sigma }^{\prime }:E\to [q]$ 可以等价地写成向量

$${\sigma }^{\prime }=(k_1,k_2,\dots ,k_m),k_i={\sigma }^{\prime }(e_i)\in [q].$$

由于 ${\sigma }^{\prime }$ 遍历 $[q{]}^E$，向量 $(k_1,\dots ,k_m)$ 恰好遍历笛卡尔积 $[q{]}^m$。因此证明中的内层求和可以写成多重求和：

$$\begin{array}{rl}\mathrm{LHS}& =\sum _{{\sigma }^{\prime }\in [q{]}^E}\prod _{e\in E}A(e,{\sigma }^{\prime }(e))\\ & =\sum _{k_1=1}^q\sum _{k_2=1}^q\cdots \sum _{k_m=1}^q\prod _{i=1}^{m}A(e_i,k_i).\end{array}$$

每个因子 $A(e_i,k_i)$ 只依赖对应的变量 $k_i$，与其余求和变量无关。利用有限次乘法分配律，可以逐层将无关因子移出求和号：

$$\begin{array}{rl}\mathrm{LHS}& =\sum _{k_1=1}^{q}A(e_1,k_1)\left[\sum _{k_2=1}^{q}A(e_2,k_2)\left[\cdots \left[\sum _{k_m=1}^{q}A(e_m,k_m)\right]\cdots \right]\right]\\ & =\left(\sum _{k_1=1}^{q}A(e_1,k_1)\right)\left(\sum _{k_2=1}^{q}A(e_2,k_2)\right)\cdots \left(\sum _{k_m=1}^{q}A(e_m,k_m)\right)\\ & =\prod _{e\in E}\left(\sum _{k\in [q]}A(e,k)\right).\end{array}$$

所以，这一步并不是对任意求和与乘积进行交换；它成立的关键是求和域 $[q{]}^E$ 是各边状态空间的笛卡尔积，并且每个因子只依赖一条边上的求和变量。