期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Khrapchenko's classical lower bound n 2 on the formula size of the parity function~ f can be interpreted as designing a suitable measure of subrectangles of the combinatorial rectangle f − 1 (0) f − 1 (1) . Trying to generalize this approach we arrived at the concept of \emph{convex measures}. We prove the negative result that convex measures are bounded by O ( n 2 ) 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.
f − 1 (1) . Trying to generalize this approach we arrived at the concept of \emph{convex measures}. We prove the negative result that convex measures are bounded by O ( n 2 ) 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.
