文章基本信息

标题：Complexity and Probability of some Boolean Formulas
本地全文：下载
作者：Petr Savicky
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：For any Boolean function f let L(f) be its formula size complexity in the basis 1 . For every n and every kn2 , we describe a probabilistic distribution on formulas in the basis 1 in some given set of n variables and of the size at most l(k)=4k. Let pnk(f) be the probability that the formula chosen from the distribution computes the function f. For every function f with L(f)l(k), where =log4(32) , we have pnk(f)0. Moreover, for every function f, if pnk(f)0, then (4n)−l(k)pnk(f)c−l(k)14 where c1 is an absolute constant. Although the upper and lower bounds are exponentially small in l(k), they are quasipolynomially related whenever l(k)ln(1)n. The construction is a step towards developping a model appropriate for investigation of the properties of a typical (random) Boolean function of some given complexity.
关键词：Boolean formulas, complexity, probability