<p>What is the lowest known lower-bound on the number of NAND gates needed in order to perform an arbitrary deterministic computation with a fixed length input and output?</p>

CC BY-SA 3.0
2011-04-24T14:50:01.163Z
There is no *least lowerbound*. The question does not make sense in its current form for other reasons. The lease number of gates one need to be able to build a circuit for an arbitrary function on n bits is exponential by simple counting, check the Shannon's proof for usual gates. Closing the question as off-topic since it is not research level in its current form (also could be closed as not a real question).
Kaveh
CC BY-SA 3.0
2011-04-24T18:14:41.803Z
I'd vote to reopen. Might it not be that for NAND gates, Shannon's lower bound could be refined, in terms of leading constants?
arnab
CC BY-SA 3.0
2011-04-24T20:06:16.397Z
you perhaps meant _best_ (i.e. largest) lower bound?  You seem to be asking how big a circuit is required to represent a given Boolean function with $n$-bit input.  If so, see http://en.wikipedia.org/wiki/Circuit_complexity
András Salamon
CC BY-SA 3.0
2011-04-24T21:31:44.387Z
@arnab, I don't think the question should be reopened in its current form since it is not clear what is being asked. Your interpretation might be research-level but that does not seem to be the questions at the moment. ps: note that constant numbers of NAND gates can simulate the standard gates so there can't be a super constant improvement for NAND. It seems to me that OP is not aware of the basic result by Shannon, therefore this is not a research-level question until further clarification by OP.
Kaveh
<cc.complexity-theory><lower-bounds><circuit-complexity>
Circuit lower bound for NAND based arbitrary deterministic computation
dan_waterworth
# Circuit lower bound for NAND based arbitrary deterministic computation

(Asked by: username_0 on 2011-04-24)

What is the lowest known lower-bound on the number of NAND gates needed in order to perform an arbitrary deterministic computation with a fixed length input and output?

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity
> **Comments:**
> **username_1**: There is no *least lowerbound*. The question does not make sense in its current form for other reasons. The lease number of gates one need to be able to build a circuit for an arbitrary function on n bits is exponential by simple counting, check the Shannon's proof for usual gates. Closing the question as off-topic since it is not research level in its current form (also could be closed as not a real question).  
> **username_2**: I'd vote to reopen. Might it not be that for NAND gates, Shannon's lower bound could be refined, in terms of leading constants?  
> **username_3**: you perhaps meant _best_ (i.e. largest) lower bound?  You seem to be asking how big a circuit is required to represent a given Boolean function with $n$-bit input.  If so, see http://en.wikipedia.org/wiki/Circuit_complexity  
> **username_1**: @arnab, I don't think the question should be reopened in its current form since it is not clear what is being asked. Your interpretation might be research-level but that does not seem to be the questions at the moment. ps: note that constant numbers of NAND gates can simulate the standard gates so there can't be a super constant improvement for NAND. It seems to me that OP is not aware of the basic result by Shannon, therefore this is not a research-level question until further clarification by OP.  

---

## 0 answers

