ECCC-Report TR99-045https://eccc.weizmann.ac.il/report/1999/045Comments and Revisions published for TR99-045en-usMon, 22 Nov 1999 18:17:47 +0200
Paper TR99-045
| Circuit Minimization Problem |
Valentine Kabanets,
Jin-Yi Cai
https://eccc.weizmann.ac.il/report/1999/045We 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.
Mon, 22 Nov 1999 18:17:47 +0200https://eccc.weizmann.ac.il/report/1999/045