TR99-045 Authors: Valentine Kabanets, Jin-Yi Cai

Publication: 22nd November 1999 18:17

Downloads: 3813

Keywords:

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.