New answers tagged circuits
2
votes
Can you compute a majority function of n-bits using an O(n) size circuit?
Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion.
At the $i$-th level of the tree you're dealing with numbers with at most $i+1$ bits.
Hence the number of gates ...
0
votes
3 bit binary multiplier?
For an n-bit by n-bit multiplier you use $n^2$ ANDs which each give a single bit in some bit position. For example in a 64 bit multiplier $x_{52} and $y_{22} would be a bit in position 74.
You arrange ...
Top 50 recent answers are included
Related Tags
circuits × 296complexity-theory × 151
logic × 29
boolean-algebra × 25
digital-circuits × 18
lower-bounds × 15
complexity-classes × 14
turing-machines × 13
quantum-computing × 13
algorithms × 11
reference-request × 11
satisfiability × 10
time-complexity × 9
computability × 9
reductions × 9
computation-models × 8
polynomial-time × 8
computer-architecture × 7
space-complexity × 7
boolean-complexity × 7
np-complete × 6
arithmetic × 6
sequential-circuit × 5
graphs × 4
optimization × 4