ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-045 | 16th November 1999 00:00

Circuit Minimization Problem

RSS-Feed




TR99-045
Authors: Valentine Kabanets, Jin-Yi Cai
Publication: 22nd November 1999 18:17
Downloads: 1508
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint