EDAboard.com | EDAboard.de | EDAboard.co.uk | WTWH Media

elektroda.net NewsGroups Forum Index - Synthesis - **Complexity of minimal circuit**

Guest

Thu Jan 20, 2005 10:31 am

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"

}

Guest

Thu Jan 20, 2005 12:08 pm

In article <41ef886a$0$11352$3b214f66_at_aconews.univie.ac.at>,

Roderick Bloem <roderick.bloem_at_ist.tu-graz.ac.at> wrote:

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!

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.

--

Daniel Jiménez djimenez_at_cs.utexas.edu

"I've so much music in my head" -- Maurice Ravel, shortly before his death.

" " -- John Cage

Guest

Sun Jan 23, 2005 4:19 am

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

elektroda.net NewsGroups Forum Index - Synthesis - **Complexity of minimal circuit**