Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table
复制标题
给定真值表时最小化析取范式公式和 AC0 电路
DOI：
10.1137/060664537
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Saks
中科院分区：
文献类型：
--
作者：
Eric Allender;L. Hellerstein;Paul McCabe;T. Pitassi;M. Saks
对于电路类$R$，基本计算问题Min-R要求以真值表形式呈现的布尔函数的最小$R$大小。这个问题的突出例子包括Min-DNF，它询问作为真值表呈现的给定布尔函数是否具有$k$项析取范式（DNF），以及Min-Circuit（也称为最小电路大小问题（MCSP）），它询问作为真值表呈现的布尔函数是否具有大小$k$布尔电路。我们提出了一个新的约简，证明Min-DNF是NP-完全的。它明显比Masek [Some NP-Complete Set Covering Problems，manuscript，1979]的已知约简简单，Masek的约简来自Circuit-SAT。然后，我们给出了一个更复杂的减少，产生的结果，Min-DNF不能近似到一个小于$（\log N）^{\gamma}$的因子内，对于一些常数$\gamma>0$，假设NP不包含在准多项式时间。集合覆盖的标准贪婪算法在实践中经常被用来近似Min-DNF。Min-DNF是否可以近似到$o（\log N）$的因子内的问题仍然是开放的，但是我们构造了一个Min-DNF的实例，在该实例上，贪婪算法产生的解$\Omega（\log N）$大于最优解。最后，我们转向近似电路大小的问题，稍微更一般的电路类。DNF公式是深度为2的AND和OR门电路。深度-$d$电路由$AC^0_d$表示。我们表明，这是很难近似的大小$AC^0_d$电路（足够大的$d$）下的密码学假设。
For circuit classes $R$, the fundamental computational problem Min-R asks for the minimum $R$-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a $k$-term disjunctive normal form (DNF), and Min-Circuit (also called the minimum circuit size problem (MCSP)), which asks whether a Boolean function presented as a truth table has a size $k$ Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [Some NP-Complete Set Covering Problems, manuscript, 1979], which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than $(\log N)^{\gamma}$, for some constant $\gamma>0$, assuming that NP is not contained in quasi-polynomial time. The standard greedy algorithm for Set Cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of $o(\log N)$ remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is $\Omega(\log N)$ larger than optimal. Finally, we turn to the question of approximating circuit size for slightly more general classes of circuits. DNF formulas are depth-two circuits of AND and OR gates. Depth-$d$ circuits are denoted by $AC^0_d$. We show that it is hard to approximate the size of $AC^0_d$ circuits (for large enough $d$) under cryptographic assumptions.