NAND

Question 1

Every function F: {0,1}^n –> {0,1} can be computed by a ___ line NAND program

Answer 1

For every function F: {0,1}^n –> {0,1}, there exists an O(2^n/n) line NAND program computing F.

Why?
F is a program tying inputs to outputs

the lookup function from {0,1}^n –> {0,1}^m takes 4m2^n lines of code

Why for LOOKUP?
4 lines for the base MUX case, multiply by m for each bit of the output, each LOOKUP_n = 2 runs of LOOKUP_(n-1)

Question 2

How many lines of code does LOOKUP_k need in NAND?

Answer 2

the lookup function from {0,1}^n –> {0,1}^m takes 4m2^n lines of code

Why?
4 lines for the base MUX case

multiply by m for each bit of the output

each LOOKUP_n = 2 runs of LOOKUP_(n-1)

Question 3

How many lines of code does MUX need?

Answer 3

4 lines

Question 4

What is LOOKUP_k? input parameters, high level function

Answer 4

LOOKUP_k (x, i)
= LOOKUP_k(x_0, … x_(2^k-1), i_0, …, i_(k-1)) =
the first 2^k bits inputted are the elements of the string x, the last k bits are the index of the string we’re accessing.

For strings represented in k bits (i.e. for lists of size 2^k), find the value of any index (0 - k)

Question 5

How do you the indices 0, …, k-1 in binary?

Answer 5

With log(k) bits

Question 6

How many lines of NAND code does LOOKUP_k need? [Big O Notation]

Answer 6

LOOKUP_k = LOOKUP_1 (LOOKUP_(k-1), LOOKUP_(k-1), i_(k-1))

O(k) = 4 + 2*O(k-1)
…
O(1) = 4

O(k) = 4* (2^k - 1) < 4*2^k

Total: 4*2^k lines

Question 7

How many lines of NAND code to represent XOR?

Answer 7

4 lines

Question 8

How many lines of NAND code to represent AND?

Answer 8

2 lines (negation)

Question 9

How many lines of NAND code to represent negation?

Answer 9

1 line (a NAND a)

Question 10

How many lines of NAND code to represent EQUALS_n (takes two strings of length n)?

Answer 10

5 lines (negate, XOR)

Question 11

How many lines of NAND code to represent LOOKUP_n?

Answer 11

4*2^n

Question 12

How many lines of code to represent a function F: {0,1}^n –> {0,1}^m

Answer 12

4m2^n lines

O(m*2^n)

there’s an improvement:

O(m*2^n/n)

Question 13

How do many lines is MAJ?

Answer 13

v_0 := x_0 NAND x_1 
v_1 := x_0 NAND x_2 
v_2 := x_1 NAND x_2 
v_3 := v_2 NAND v_1
notv_3 := v_3 NAND v_3 
y_0 := notv_3 NAND v_0

Question 14

If a program has n lines, how many variables can the program have?

Answer 14

< 3s variables

Question 15

What is |Size(s)|? How many programs are possible in Size(s)?

Answer 15

at most 2^(4slogs)

Question 16

How many functions are there st F: {0,1}^n –> {0,1}?

Answer 16

2^(2^n)

map any input to a choice between 0 and 1 as outputs

Question 17

How many functions are there st F: {0,1}^n –> {0,1}^m?

Answer 17

(2^m)^(2^n)

map any input to a choice among 2^m outputs

Question 18

How many functions are there mapping F: A–>B?

Answer 18

|B|^|A|

map any input to the choice of |B| outputs

Question 19

What’s the lower bound for # of lines to compute a function F: {0,1}^n –> {0,1}?

Answer 19

there exists a function F: {0,1}^n –> {0,1} that uses at most 2^n/(100n) lines

Question 20

How many lines of code does the composition of functions F and G have?

Answer 20

lines of F + lines of G

Question 21

How many lines of code does the parallel computation of functions F and G have?

Answer 21

lines of F + lines of G

Question 22

Every EVALsmn(P,x) can be written as a NAND program with O(__) lines

Answer 22

Every EVALsmn(P,x) can be written as a NAND program with O(sslogs) lines. s lines, s < t/3 for t variables, logs < log t/3 for checking equality which is logt bits to check for each variable update. (Lecture, Thm 2)

Question 23

How many functions are in Size(s), what is |Size(s)|?

Answer 23

s line program is around s variables. s variables require logs bits each. s*logs bits to represent all variables. Each bit can be 1 or 0.

|Size(s)| <= 2^O(slogs)

Question 24

What is the minimum number of NAND lines you need to compute a function: F:{0,1}^n –> {0,1}?

Answer 24

For every function F: {0,1}^n –> {0,1}, there is an O(2^n/n) line NAND program computing F

number of lines = O(2^n/n)

(Lecture, Thm 1)

Question 25

Every function F:{0,1}^n –> {0,1} can be written with O(2^n/n) but when does that break? How many lines is too few lines?

Answer 25

There exists F:{0,1}^n –> {0,1} that is not in Size(2^n/100n)! The constant that breaks the camel’s back of representing all functions F in 1/100 * 2^n/n lines

Question 26

How do you write OR in NAND?

Answer 26

3 lines OR(a,b) = !a NAND !b

Question 27

How many NAND lines for a function F: {0,1}^n –> {0,1}^m?

Answer 27

at most O(m*2^n)

Question 28

How do you compute multiplication of two bits?

Answer 28

AND

Question 29

How do you compute addition of two bits?

Answer 29

XOR for the output, MAJ for the carry

Question 30

What is LOOKUP k?

Answer 30

The length of the array being searched is 2^k

Question 31

If you have an array of size J, how many lines of code do you need to find elements of the array?

Answer 31

Assuming each element of the array is 1 bit; finding a variable corresponds to LOOKUP_logJ which requires 4*2^logJ lines of code which is 4J lines of code

Assuming each element of the array is m bits; finding a variable corresponds to m instances LOOKUP_logJ which requires 4m*2^logJ lines of code which is 4mJ lines of code

Question 32

How do you update T variables?

Answer 32

the IDs of the T variables require logT bits

for each of T variables, you compute bit by bit if the variable is equal to target. Overall, you check TlogT bits. You need TlogT lines

Question 33

If you have an input output table of a function {0,1}^n –> {0,1}^m, how many lines of code does it take to evaluate?

Answer 33

Requires at most O(m*2^n/n) lines of code to evaluate with a lookup_logn function.

Note, not all functions can be computed in m*2^n/100n lines of code

Question 34

If you have an s-line program representations of a function {0,1}^n –> {0,1}^m, how many lines of code does it take to compute evaluate?

Answer 34

You can evaluate the function in O(s^2logs) lines of code.

s lines * s variables per line * logs bits to represent/ check bit by bit each variable

Overall, s^2logs lines of code to evaluate

Question 35

If you have an S-bit program representation of a function, how many lines of code does it take to compute evaluate?

Answer 35

O(S^2) (see proof for s line program where S=slogs)