The Minimum Equivalent DNF Problem and Shortest Implicants

原文：doi:10.1109/SFCS.1998.743506 · Umans, FOCS 1998

摘要： 我们证明了最小等价 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$ 一个，总长度就为

min_C\{|vars(C)\backslash W|+m|vars(C)\cap W| \}

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

f = \bigvee_{j=1}^{|S_1|} (s_{1j} \land z_1) \vee \left(\bigvee_{i=2}^{n-1} \bigvee_{j=1}^{|S_i|} (\overline{z_{i-1}} \land s_{ij} \land z_i)\right) \vee \bigvee_{j=1}^{|S_n|} (\overline{z_{n-1}} \land s_{nj})

其中 $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$ ，定义

\phi'=\phi_nw_1w_2...w_{m'}\lor \bigvee_{i\in[m]}\phi_iw_1w_2...w_{i-1}w_{i+1}...w_{m'}

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

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

\phi''=t_nw_1...w_{m'}\lor\bigvee^m_{i=i}s_i'=Cw_1...w_{m'}\lor\bigvee^m_{i=1}s_i'

其中 $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，则要证明下面：

对于所有的 $i$ ， $\sigma$ 包含 $s_i''$ 使得 $s_i'\subseteq s_i''$
$s_i''$ 的总长度至少为 $\sum_{i=1}^m|s_i'|$
$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$ 。