分辨率指数下限...替代证据？

Question

我正在阅读通过Haken的瓶颈方法的分辨率证明系统指数下限，如arora和barak的计算复杂性所展示的鸽舍原则：现代方法，第15章。但是，我没有就像这本书中的证明是如何呈现的，我遇到了一些困难。

有人知道呈现同一证明的替代来源吗？我知道有不同的技术来显示分辨率的指数下限，但我想要基于鸽孔原理的东西。这本书的短语只是令人困惑的是。

Answer 1

如果您不喜欢Arora和Barak的演示，您可以随时查看Haken的原始纸张。

然而，通过分辨率宽度，分辨率下限的现代方法是在 Ben-Sasson和Wigderson的古典纸张。您还可以在各种讲义中找到博览会，例如通过 jakobnordström。