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?


closed as off topic by Kaveh Apr 24 '11 at 14:50

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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