一本关于组合学的精彩绝伦的书

Stasys Jukna是“极端组合在计算机科学中的应用”一书的作者。

他这本书的结构很棒。这份材料很有用，而且呈现得很好。与其对他的书添加更多的一般性评论，我们认为我们可以突出一个很小的部分-关于单调电路下限的部分。开始了。下面的所有内容都直接基于他的讨论。任何错误或误导性的评论都是我们的。

固定输入大小，并考虑的子集的某些属性。让我们确切地知道什么时候拥有房产。我们可以把它想象成一个布尔函数。你认为这个性质很难计算--你怎么证明这一点呢？

一般来说，我们没有工具，但是如果属性是单调的，那么有一些强大的方法。召回单调意味着，如果这样，那么任何集合都仍然具有该属性。例如，可能包含至少一半的元素。元素的数量不可能是偶数。另一个例子是当以析取范式(DNF)给出时，

其中每一项都是变量的合取。每一个都可以看作是的子集。那么如果且仅当对某些人来说。每个单调函数也有一个合取范式(CNF)。

其中每个子句都是变量的析取。那么，如果且仅当所有的问题是，所涉及的条款和条款的数量可能是巨大的。这些条款可能有不同的大小。在给定最大子句大小的CNF的情况下，我们精确地为大小的子句的连接词编写，并为其余的子句编写。我们同样为dNFS编写和。

下界方法是关于的单调电路的大小。也就是说电路只能使用闸门和，而不能使用其他类型的闸门，特别是不能使用闸门。当然，如果没有小的单调电路，那么它也没有小的DNF或CNF公式。

下限技术所基于的巧妙事实是，如果确实有小的单调电路，那么我们可以用各种可定制的方式在CNF和DNF之间“包装”它：

定理1(非正式)对于每个具有小的单调电路的人，我们可以找到最大子句大小的CNF和最大项大小的DNF，使得