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

1. Intro

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

1.1. Previous Work

有很多讨论电路简化/DNF最小化的文章，但是基本没有证明它复杂性的相关工作。Hemaspaandra and Wechsung的工作证明了MIN-DNF是$P_2^{NP}$-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\to f$为永真式，则称$C$是$f$的蕴含项。

2.1. Problems

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

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

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

2.2. Tools

观察：

• 如果$C_1$是$f$的一个蕴含项，$C_2$是满足$C_1\subseteq C_2$的一个合取范式，则$C_2$也是$f$的一个蕴含项
• $f=f_1\wedge f_2$，则$f$的蕴含项也是$f_1,f_2$的蕴含项
• $f=f_1\vee 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^{\prime }(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^{\prime })=mi{n}_c\{|vars(c)\backslash W|+m|vars(C)\cap W|\}$，其中$C$是$f$的所有蕴含项，$SI(f)$是指$f$的最小蕴含项的长度
• 如果$C$是$f$的蕴含项且$vars(C)\cap W=\varnothing$，则$C$是$f^{\prime }$的蕴含项

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

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

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

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

引理： 设$f$是一个$(S_1,...,S_n)$的选择公式，且令$C$是一个只包含${\bigcup }_i{S}_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}}$: 给定析取范式$\varphi ={\bigvee }_{i\in [n]}{t}_i$，是否存在$\varphi$的蕴含项$C$满足(1)$|C|\le k$；(2)$C\subseteq t_n$？

Claim 1： $\exists x\forall y.\varphi (x,y)\in \text{2QBF}$， 当且仅当${\varphi }^{\prime }$有一个大小为$m$的蕴含项$C^{\prime }$满足$\forall i\in [m].C^{\prime }\cap V_i\ne \varnothing$。${\varphi }^{\prime }$是将$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.\varphi (x,y)\in \text{2QBF}$，则存在$x$的真值指派使得$\varphi (x,y)$为永真式，即有一个大小为$m$的$\varphi$的蕴含项$C$，每个变量都在$\{x_1,{\bar{x}}_1,...,x_m,{\bar{x}}_m\}$中。根据上面替换，替换后的蕴含项为$C^{\prime }$，替换后的命题为${\varphi }^{\prime }$，显然$C^{\prime }$是${\varphi }^{\prime }$的蕴含项。反向同理，$C^{\prime }$定义了一个$x$的真值指派使得$\varphi (x,y)$永真，故$\exists x\forall y.\varphi (x,y)\in 2QBF$.

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

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

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

证明： 由上述声明得知，一个输入为$⟨{\varphi }^{\prime \prime },m⟩$的${\text{Short-IML}}^{\text{CORE}}$为真当且仅当 输入为$⟨\varphi ⟩$的$\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}}$的一个输入$⟨\varphi ,k⟩$， 因为$\varphi =\varphi \wedge ┐{\varphi }_n\vee {\varphi }_n$，定义

其中$m^{\prime }=max\{m,k+1\}$。可以注意到上面的式子实际上就是把$\varphi \wedge ┐{\varphi }_n$拆开为一个析取范式。

Claim3： 如果$C\in {\varphi }_n$是$\varphi$的一个蕴涵项，则

其中$s_i^{\prime }=s_i{w}_1..w_{m^{\prime }}$，$s_i$是${\varphi }^{\prime }$展开为DNF的项。令$k^{\prime }=k+m^{\prime }+{\sum }_{i=1}^m|s_i^{\prime }|$，则需要证明的MIN-DNF的输入就是$⟨{\varphi }^{\prime \prime },k^{\prime }⟩$。

证明： 因为$\varphi ={\varphi }^{\prime \prime }$，则$C$也是${\varphi }^{\prime \prime }$的蕴含项，且$C{w}_1...w_{m^{\prime }}$也是，且长度不超过$k^{\prime }$。设一个$\sigma ={\bigvee }_{i=1}^m{s}_i^{\prime \prime }$是${\varphi }^{\prime \prime }$的一个长度最大为$k$的等价DNF，则要证明下面：

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

因此，若$⟨\varphi ,k⟩\in {\text{Short-IML}}^{\text{CORE}}$，则$⟨{\varphi }^{\prime \prime },k⟩\in \text{MIN-DNF}$。证明完成了一个方向。

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

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