Complexity of minimal circuit

[Roderick Bloem]

I am looking for a theoretical upper and lower bound on the complexity
of constructing a multi-level Boolean circuit. We are given a function
f and want to construct a circuit with a minimal number of gates.
Lawler [Lawler-64] calls this an absolutely minimal form.

I am being deliberately vague about the gates allowed and the form of
the input. If those details are important, please let me know.

I would be perfectly happy with a reference rather than a complete
explanation.

Thanks!

Roderick Bloem

@ARTICLE{Lawler-64,
AUTHOR = "E. L. Lawler",
TITLE = "An Approach to Multilevel Boolean Minimization",
JOURNAL = jacm,
VOLUME = 11,
NUMBER = 3,
MONTH = jul,
YEAR = 1964,
PAGES = "283-295"
}

[Daniel A. Jimenez]

Post by Roderick Bloem
I am looking for a theoretical upper and lower bound on the complexity
of constructing a multi-level Boolean circuit. We are given a function
f and want to construct a circuit with a minimal number of gates.
Lawler [Lawler-64] calls this an absolutely minimal form.
I am being deliberately vague about the gates allowed and the form of
the input. If those details are important, please let me know.
I would be perfectly happy with a reference rather than a complete
explanation.
Thanks!

This problem is hard for NP^NP by reduction from Minimum Equivalent Boolean
Expression. That is, it's very hard. See Garey and Johnson for details
on this complexity class. Also see discussion of this topic in previous
articles on comp.theory (Google for NP^NP).

For a VLSI class project years ago, I solved this problem for every Boolean
function of up to 4 variables with certain sets of gates. It took many days
of CPU time. Basically, you enumerate all non-isomorphic Boolean circuits
using n gates and test each one to see what truth table it generates.
Start with n=1 and stop when you find what you're looking for.

Let us know if you find a lower bound tighter than polynomial.

[Scott Aaronson]

No, that's wrong. The Minimum Equivalent Circuit problem is certainly
NP-hard, and is in NP^NP, but is not known to be either in NP or hard
for NP^NP. This has been a longstanding open problem. One of the few
things we know, due to Bshouty, Cleve, et al., is that a ZPP^NP
algorithm can produce an equivalent circuit that is minimal up to a
polynomial factor -- so the problem is not NP^NP-hard to approximate,
unless the polynomial time hierarchy collapses. Same goes for Minimum
Equivalent Boolean Expression.

To answer Roderick's question, the form of the input really does matter
here. In particular, if the function is specified by a truth table of
size N=2^n, then it is not even known how to find the minimum circuit
in time polynomial in N. On the other hand, unlike the minimum
equivalent circuit problem, this version is clearly *in* NP. It's not
known to be NP-complete, but solving it would let you break
pseudorandom generators and therefore factor integers faster than we
know how to do. This is all discussed in a paper by Kabanets and Cai.
(I didn't track down the references, but you can find them through
Google.)

Hope that helps,
Scott Aaronson