1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Kaveh Apr 24 '11 at 14:50
  • $\begingroup$ 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? $\endgroup$ – arnab Apr 24 '11 at 18:14
  • 1
    $\begingroup$ 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 en.wikipedia.org/wiki/Circuit_complexity $\endgroup$ – András Salamon Apr 24 '11 at 20:06
  • 2
    $\begingroup$ @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. $\endgroup$ – Kaveh Apr 24 '11 at 21:31