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.