摘要： 我们证明了最小等价DNF问题是$\sum_2^P$-完全的，解决了Stockmeyer留下的猜想。我们还考虑了第二层多项式结构中相关优化问题的复杂性和近似性，即寻找布尔函数的最短蕴含项。我们证明，当输入作为DNF给出时，对高于 $coNP$ 的复杂性类使用$O(log^2n)$-limited非确定图灵机可以完成这个问题。当输入作为公式或电路给出时，这个问题是$\sum_2^P$-完全的，并且在分别在因子$n^{1/2-\epsilon}$和$n^{1-\epsilon}$是$\sum_2^P$-hard的。

1. Intro

逻辑综合领域等很多领域都在研究电路最小化问题，这个问题自从Stockmeyer的多项式层次相关的论文提出一直被猜测是$\sum_2^P$-完全的，但是一直没有被证明。本文证明了MIN-DNF问题是$\sum_2^P$-完全的，并且对于DNF形式给出的输入可以用一个复杂性不高于$O(log^2n)$的非确定图灵机解决。

1.1. Previous Work

有很多讨论电路简化/DNF最小化的文章，但是基本没有证明它复杂性的相关工作。Hemaspaandra and Wechsung的工作证明了MIN-DNF是$P^{NP}_2$-hard的（$\Delta_2^P$?）或NP-hard的。

1.2. Practical Significance

In the more common case of NP-complete problems, a completeness result removes the likelihood of an efficient exact solution and justifies a concentration of effort on approximate or heuristic solutions.

虽然有上面的论断，但是用启发式或者近似的方法，也都要求解决“子问题”的时候要有精确性，如逻辑综合程序ESPRESSO。研究这些子问题的复杂度和高效性也是很重要的。

2. Preliminaries

设$C$是合取项，$f$是一个布尔函数，满足$C \rightarrow f$为永真式，则称$C$是$f$的蕴含项。

2.1. Problems

Minimum equivalent DNF($\text{MIN-DNF}$): 给定一个析取范式$\phi$和一个整数$k$，是否存在一个等价于$\phi$且长度不超过k的析取范式？

$\text{Short-IMP}^{DNF}$：析取范式$\phi$有大小不超过$k$的蕴含项。

$\text{QSAT}_2$：给定分离的变量集$X_1, X_2$，以及一个$\text{3-DNF}$公式$\phi$，使得$X_1 \cup X_2, \exists X_1\forall X_2 \phi$。

2.2. Tools

观察：

• 如果$C_1$是$f$的一个蕴含项，$C_2$是满足$C_1\subseteq C_2$的一个合取范式，则$C_2$也是$f$的一个蕴含项
• $f = f_1 \land f_2$，则$f$的蕴含项也是$f_1, f_2$的蕴含项
• $f=f_1\lor f_2$，则$f_1$的蕴含项也是$f$的蕴含项

引理一： 设$f(x_1, ..., x_n)$是一个布尔函数，$W\subseteq \{x_1,...,x_n\}$为”set of variables to weight”（会被后面的Boolean parity function处理的变量）。定义$f'(h_1, ..., h_n)$，其中$h_i$是如下定义：如果$x_i\in W$，则$h_i$是$m$个变量的布尔奇偶校验函数（把他们相异或）（原文：“an independent copy of the Boolean parity function on m variables”），否则$h_i=x_i$，则下面两个声明成立：

• $\text{SI}(f')=min_c\{|vars(c)\backslash W|+m|vars(C)\cap W| \}$，其中$C$是$f$的所有蕴含项，$SI(f)$是指$f$的最小蕴含项的长度
• 如果$C$是$f$的蕴含项且$vars(C)\cap W=\empty$，则$C$是$f'$的蕴含项

证明： 第二个声明比较简单，因为如果$vars(C)\cap W=\empty$，那么其中包含的变量在$f'$里也都包含。对于第一个证明，假设有$f'$的最小蕴含项$C'$，对于每个$i$，$h_i$要么被$C'$强制指定为0或1，要么是自由的（在与$C'$一致的赋值中可能任意取0或取1）。如果是被强制指定的$h_i$，则$C'$一定要包含$h_i或\urcorner h_i$，如果$x_i\notin W$，那$C'$就要用m项表示，否则只要用一个。如果是自由的$h_i$，则只需要包含$x_i$或者$\urcorner x_i$一个，总长度就为

选择公式： 给定$n\geq2$个不相交变量集合$S_1, ..., S_n$，选择公式$f$定义为：

其中$s_{ij}$是$S_i$中的变量，$z$是新变量。

$\bigvee_{j=1}^{|S_1|} (s_{1j} \land z_1)$表示$S_1$中至少有一个变量和$z_1$同时为真；$\bigvee_{i=2}^{n-1} \bigvee_{j=1}^{|S_i|} (\overline{z_{i-1}} \land s_{ij} \land z_i)$表示从第二个开始，$z_{i-1}$和$s_{ij}z_i$必须同真假，保证变量的选择依赖于前一个集合的选择；$\bigvee_{j=1}^{|S_n|} (\overline{z_{n-1}} \land s_{nj})$表示$z_{n-1}$必须为假且$S_n$中某个变量必须为真。

引理： 设$f$是一个$(S_1, ..., S_n)$的选择公式，且令$C$是一个只包含$\bigcup_iS_i$中变量的合取式。当且仅当$vars(C)\cap S_i$对所有$i$至少有一个的时候，$C$是$f$的一个蕴含项。

证明： 设$C$是$f$的蕴含项。假设$C$中不包含任何$S_i$的变量，则将$C$中所有变量设为1，而所有$k>i$的$z_k$设为0，根据上述选择公式可知中间项为假而$C$为真，故$C$不是$f$的蕴含项，与前设矛盾。

3. Complexity of DNF Minimization

减少DNF长度的一个显然的方法是，去掉其中的一个变量，然后验证它是否是原DNF的一个蕴含项。如果有一个$NP$的神谕机用于验证，上述方法显然是多项式时间的。但是需要指出的是，结果DNF的长度实际上取决于去除变量的顺序。为了考虑能否取得一个最短的DNF，考虑下面的更特殊的问题：

$\text{Short-IML}^{\text{CORE}}$: 给定析取范式$\phi=\bigvee_{i\in [n]}t_i$，是否存在$\phi$的蕴含项$C$满足(1)$|C|\leq k$；(2)$C\subseteq t_n$？

Claim 1： $\exists x\forall y.\phi(x,y)\in \text{2QBF}$， 当且仅当$\phi'$有一个大小为$m$的蕴含项$C'$满足$\forall i\in[m].C'\cap V_i\neq\empty$。$\phi'$是将$x_1, ..., x_m$替换成$w_1,...,w_m$，$\bar x_1,...,\bar x_m$替换成$v_1,...,v_n$，$V_i=\{w_i, v_i\}$。

证明： 若$\exists x\forall y.\phi(x,y)\in \text{2QBF}$，则存在$x$的真值指派使得$\phi(x,y)$为永真式，即有一个大小为$m$的$\phi$的蕴含项$C$，每个变量都在$\{x_1, \bar x_1,...,x_m,\bar x_m\}$中。根据上面替换，替换后的蕴含项为$C'$，替换后的命题为$\phi'$，显然$C'$是$\phi'$的蕴含项。反向同理，$C'$定义了一个$x$的真值指派使得$\phi(x,y)$永真，故$\exists x\forall y.\phi(x,y)\in 2QBF$.

Claim 2： $\phi''=(f\land \phi')\lor S$有一个长度最多为$m$的蕴含项$C\subseteq V$，当且仅当$\exists x\forall y.\phi(x,y)\in \text{2QBF}$.

证明： 设$\phi''$有一个长度最长为$m$的蕴含项$C$，则$C$至少包含每一个$V_i$中的一项，原因如Claim 1所示。反向，设$\phi''$有一个长度不超过$m$的蕴含项$C''\subseteq V$，如果$\exists i.V_i$中两个元素都不在$C''$中，则根据引理2，$C''$不是$\phi$的蕴含项，所以$C''$不是$\phi''$的蕴含项，错误。

命题： $\text{Short-IML}^{\text{CORE}}$是$\sum_2^P$-完全的。

证明： 由上述声明得知，一个输入为$\left<\phi'', m\right>$的$\text{Short-IML}^{\text{CORE}}$为真当且仅当 输入为$\left<\phi\right>$的$\text{2QBF}$的问题为真。而$\text{iQBF}$问题是$\sum_i^P$-完全的，所以$\text{Short-IML}^{\text{CORE}}$问题是$\sum_2^P$-完全的。

命题： $\text{MIN-DNF}$是$\sum_2^P$-完全的。

证明： 考虑$\text{Short-IML}^{\text{CORE}}$的一个输入$\left<\phi,k\right>$， 因为$\phi=\phi\land\urcorner\phi_n\lor\phi_n$，定义

其中$m'=max\{m,k+1\}$。可以注意到上面的式子实际上就是把$\phi\land\urcorner\phi_n$拆开为一个析取范式。

Claim3： 如果$C\in \phi_n$是$\phi$的一个蕴涵项，则

其中$s'_i=s_iw_1..w_{m'}$，$s_i$是$\phi'$展开为DNF的项。令$k'=k+m'+\sum_{i=1}^m|s_i'|$，则需要证明的MIN-DNF的输入就是$\left<\phi'',k'\right>$。

证明： 因为$\phi=\phi''$，则$C$也是$\phi''$的蕴含项，且$Cw_1...w_{m'}$也是，且长度不超过$k'$。设一个$\sigma=\bigvee_{i=1}^m s_i''$是$\phi''$的一个长度最大为$k$的等价DNF，则要证明下面：

1. 对于所有的$i$，$\sigma$包含$s_i''$使得$s_i'\subseteq s_i''$
2. $s_i''$的总长度至少为$\sum_{i=1}^m|s_i'|$
3. $s_i''$没有覆盖所有$t_nw_1...w_{m'}$的赋值

因此，若$\left<\phi,k\right> \in \text{Short-IML}^{\text{CORE}}$，则$\left<\phi'',k\right> \in \text{MIN-DNF}$。证明完成了一个方向。

另一个方向上，因为$\phi''$的$w$是新引入的，所以$\phi''$中的$w$全部去除之后也要是$\phi$的蕴含项，则上面的$s'_i$也被去除了，就变回了$k$。

后面去准备MICRO了，也没怎么看懂。。。