On convex complexity measures
On convex complexity measures
复制标题
关于凸复杂性度量
DOI：
10.1016/j.tcs.2010.02.004
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Pudlák
中科院分区：
文献类型：
--
作者：
P. Hrubes;S. Jukna;A. Kulikov;P. Pudlák
赫拉普琴科关于奇偶函数f的公式大小的经典下界n2可以解释为设计了组合矩形f−1(0)×f−1(1)的一个合适的子矩形度量。为了推广这一方法，我们提出了凸测度的概念。我们证明了凸度量是O(N2)有界的否定结果，并证明了用来证明公式大小下界的几个度量是凸的。我们还证明了一类不一定是凸的测度的二次上界。
Khrapchenko’s classical lower bound n2on the formula size of the parity function f can be interpreted as designing a suitable measure of sub-rectangles of the combinatorial rectangle f−1(0)×f−1(1). Trying to generalize this approach we arrived at the concept of convex measures. We prove the negative result that convex measures are bounded by O(n2) and show that several measures considered for proving lower bounds on the formula size are convex. We also prove quadratic upper bounds on a class of measures that are not necessarily convex.