文章基本信息

标题：A Note on the Minimum Number of Negations Leading to Superpolynomial Savings
本地全文：下载
作者：Stasys Jukna
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In 1957 Markov proved that every circuit in n variables can be simulated by a circuit with at most log ( n + 1 ) negations. In 1974 Fischer has shown that this can be done with only polynomial increase in size. In this note we observe that some explicit monotone functions in P cannot be computed by a circuit of polynomial size if we allow only log n − O ( log log n ) negations.