Improvements on Khrapchenko's theorem
Improvements on Khrapchenko's theorem
复制标题
赫拉普琴科定理的改进
DOI：
10.1016/0304-3975(93)90330-v
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
E. Koutsoupias
中科院分区：
文献类型：
--
作者：
E. Koutsoupias
我们提出了 Khrapchenko 定理的改进，它给出了布尔 { ∧ ∨, Ø } 公式大小的下界。我们的主要定理给出了比原始赫拉普琴科定理更好的下界或至少相同，尽管我们知道没有任何函数可以给出大于二的改进因子。该下界是与该公式相关的某个矩阵的最大特征值。此外，我们给出了这个界限的近似值，它更容易计算，并且永远不会小于赫拉普琴科定理给出的界限。
We present an improvement of Khrapchenko's theorem which gives lower bounds for the size of Boolean { ∧ ∨, ¬ }-formulae. Our main theorem gives a better lower bound than the original Khrapchenko's theorem or at least the same, although we know of no function where it gives an improvement factor larger than two. This lower bound is the largest eigenvalue of a certain matrix associated with the formula. Moreover, we give an approximation of this bound which is easier to compute and is never smaller than the bound given by Khrapchenko's theorem.