它假设单调电路大小的下限也适用于一般布尔电路吗？

Question

a “一般”布尔（Combinatoiral）电路是一个标签的（带有标签：，或，，，，，，，out，Out），定向，非循环图，满足：

1. fan-in= 2用于和或节点
2. 粉丝-n= 1不是节点
3. 粉丝in= 0在节点
4. fan-out= 0到恰好一个节点（out节点）
5. 无限的扇出到节点的其余部分（但出oud节点）

a 单调电路是一个带布尔电路，标有0个顶点，标有“不是”。

电路的大小是它包含的“门”（带标签的顶点“（带标签”）的数量。

我们在单调电路的大小上了解许多下限，我们不知道如何在一般布尔电路上证明（例如在clique问题上的一个“）。

我的问题是：我们假设在单调电路上证明的下限还适用于等效常规布尔电路（因为它们计算单调函数），我们只是不知道如何证明它;或者我们假设\知道这些下限不适用于等效的常规布尔电路？

在后一种情况下，您是否可以向我提供由单调电路和一般布尔电路计算的单调函数的示例，同时单调电路的尺寸比普通布尔电路更具格栅？ （我已经陷入了困境的几个小时，寻求这样的一个例子，所以我相信没有这样的一个例子..）

Answer 1

évatardos给出了一个功能，它可以由多项式大小通用电路计算，但需要指数大小单调电路。电路计算到输入图的Lovászθ函数的足够好的近似值。

razborov给出了 $ n ^ {\ oomega（\ log n）} $ 下限单调电路计算二分的完美匹配功能，适用于哪种多项式尺寸通用电路存在。