在上一篇文章中，我讨论了给定数据集的 DNF 最小化的复杂性。具体来说，给定一个输入/输出对的数据集，计算与 一致的最小 DNF 有多难？在这篇文章中，我们将研究这个问题的一个变体，其中要求数据集为 中的每个点指定一个标签。DNF 真值表最小化。DNF 真值表最小化是 DNF 最小化的变体，其中输入数据集是函数 的真值表。对数据集的额外约束只能使问题变得更容易，实际上，使用 Set-Cover 的贪婪近似，可以在多项式时间内将真值表最小化近似到 的一个因子以内。第一个下界由 Masek 于 1979 年证明，表明确切的变体是 NP 难的。他的结果从未发表过，尽管后来 Umans、Villa 和
给定一个由输入/输出对组成的数据集，如何找到与数据一致的小 DNF？这个问题称为 DNF 最小化，在计算机科学史上以各种形式出现。在这篇由两部分组成的博客文章中，我将调查一些关于这个问题的复杂性的结果以及与学习 DNF 的一些联系。历史和动机。几十年来，DNF 最小化一直是逻辑综合界的核心问题。在这个领域，这个问题被称为“两级逻辑综合”。它有着悠久的历史，可以追溯到 1952 年奎因写的一篇名为“简化真值函数的问题”的论文。奎因的论文在某种程度上是对香农硕士论文“继电器和开关电路的符号分析”的回应，该论文将布尔代数引入了电路设计的研究。奎因对以下问题感兴趣。给定一个布尔函数（作为真值表），找到
