On monotone formulae with restricted depth
On monotone formulae with restricted depth
复制标题
关于深度有限的单调公式
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
M. Yannakakis
中科院分区：
文献类型：
--
作者：
M. Klawe;W. Paul;N. Pippenger;M. Yannakakis
证明了用有限制深度的单调公式表示单调布尔函数的一个层次定理。具体地说，我们证明了存在每个&sgr；<；subscrpt>；k<；/subscrpt>；-formula都有大小πω(n<；subscrpt>；1/(k−1)<；/suscrpt>；)的函数的大小为n的函数。类似的下限也适用于传递闭包和集团等具体函数。我们还证明了具有大小为n(和任意深度)的公式的任何函数都有大小为&sgr；<；subscrpt>；k<；/subscrpt>；-formula(n<；supscrpt>；1/(k−1)<；/supscrpt>；)。因此，我们的层级定理是最好的。
We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with π<subscrpt>k</subscrpt>-formula of size n for which every &sgr;<subscrpt>k</subscrpt>-formula has size exp ω(n<supscrpt>1/(k−1)</supscrpt>). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a &sgr;<subscrpt>k</subscrpt>-formula of size exp o(n<supscrpt>1/(k−1)</supscrpt>). Thus our hierarchy theorem is the best possible.