Define the function majorityn 0,1 n 0,1 as Thus, the majorityn function returns the majority vote of the inputs Show that majorityn can be computed with a O(n 2 ) size circuits b O(n log n) size circuits Recursively divide the number of inputs in half and use the result of Problem 9 23 Problem 9 23...

Solution a To compute the majorityn function with On2 size circuits we can simply comp ...

Define the function majorityn : {0,1}n {0,1} as Thus, the majorityn function returns the majority vote

Question:

Define the function majorityn : {0,1}n → {0,1} as

Jo Eai < n/2; 1 ri 2 n/2. majority , (σι, . . , αn)

Thus, the majorityn function returns the majority vote of the inputs. Show that majorityn can be computed with:

a. O(n²) size circuits.

b. O(n log n) size circuits. Recursively divide the number of inputs in half and use the result of Problem 9.23.

Problem 9.23.

Recall that you may consider circuits that output strings over {0,1} by designating several output gates. Let add_n : {0,1}²ⁿ → {0,1}ⁿ⁺¹ take two n bit binary integers and produce the n+1 bit sum. Show that you can compute the add_n function with O(n) size circuits.