Problem:
Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.
Proof idea:
The number of Boolean function is huge (i.e. exponential exponential) but the number of circuit you can make out of polynomial number of gates is smaller than that.
Proof:
The number of Boolean functions of n input can be counted by listing the output of the Boolean function output starting from
00000..000 = 0
00000..001 = 0
...
There are $ 2^n $ rows, therefore every unique bit string of length $ 2^n $ represents an unique Boolean function, so we have $ 2^{2^n} $ Boolean functions.
On the other hand, if we have a polynomial number of gates, they could be arranged in anyway, the number of circuits could be at most $ (cn^s)! < 2^{cn^s} < 2^{2^n} $, therefore, most of the circuits do require more than polynomial number of gates.
Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.
Proof idea:
The number of Boolean function is huge (i.e. exponential exponential) but the number of circuit you can make out of polynomial number of gates is smaller than that.
Proof:
The number of Boolean functions of n input can be counted by listing the output of the Boolean function output starting from
00000..000 = 0
00000..001 = 0
...
There are $ 2^n $ rows, therefore every unique bit string of length $ 2^n $ represents an unique Boolean function, so we have $ 2^{2^n} $ Boolean functions.
On the other hand, if we have a polynomial number of gates, they could be arranged in anyway, the number of circuits could be at most $ (cn^s)! < 2^{cn^s} < 2^{2^n} $, therefore, most of the circuits do require more than polynomial number of gates.
No comments :
Post a Comment