期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the complexity of the circuit minimization problem:
given the truth table of a Boolean function f and a parameter s, decide
whether f can be realized by a Boolean circuit of size at most s. We argue
why this problem is unlikely to be in P (or even in P/poly) by giving a
number of surprising consequences of such an assumption. We also argue
that proving this problem to be NP-complete (if it is indeed true) would
imply proving strong circuit lower bounds for the class E, which appears
beyond the currently known techniques.
关键词：derandomization, hard Boolean functions, natural properties, NP-completeness
