NAND Flashcards
Every function F: {0,1}^n –> {0,1} can be computed by a ___ line NAND program
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)
How many lines of code does LOOKUP_k need in NAND?
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)
How many lines of code does MUX need?
4 lines
What is LOOKUP_k? input parameters, high level function
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)
How do you the indices 0, …, k-1 in binary?
With log(k) bits
How many lines of NAND code does LOOKUP_k need? [Big O Notation]
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
How many lines of NAND code to represent XOR?
4 lines
How many lines of NAND code to represent AND?
2 lines (negation)
How many lines of NAND code to represent negation?
1 line (a NAND a)
How many lines of NAND code to represent EQUALS_n (takes two strings of length n)?
5 lines (negate, XOR)
How many lines of NAND code to represent LOOKUP_n?
4*2^n
How many lines of code to represent a function F: {0,1}^n –> {0,1}^m
4m2^n lines
O(m*2^n)
there’s an improvement:
O(m*2^n/n)
How do many lines is MAJ?
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
If a program has n lines, how many variables can the program have?
< 3s variables
What is |Size(s)|? How many programs are possible in Size(s)?
at most 2^(4slogs)
How many functions are there st F: {0,1}^n –> {0,1}?
2^(2^n)
map any input to a choice between 0 and 1 as outputs
How many functions are there st F: {0,1}^n –> {0,1}^m?
(2^m)^(2^n)
map any input to a choice among 2^m outputs
How many functions are there mapping F: A–>B?
|B|^|A|
map any input to the choice of |B| outputs
What’s the lower bound for # of lines to compute a function F: {0,1}^n –> {0,1}?
there exists a function F: {0,1}^n –> {0,1} that uses at most 2^n/(100n) lines
How many lines of code does the composition of functions F and G have?
lines of F + lines of G
How many lines of code does the parallel computation of functions F and G have?
lines of F + lines of G
Every EVALsmn(P,x) can be written as a NAND program with O(__) lines
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)
How many functions are in Size(s), what is |Size(s)|?
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)
What is the minimum number of NAND lines you need to compute a function: F:{0,1}^n –> {0,1}?
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)
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?
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
How do you write OR in NAND?
3 lines OR(a,b) = !a NAND !b
How many NAND lines for a function F: {0,1}^n –> {0,1}^m?
at most O(m*2^n)
How do you compute multiplication of two bits?
AND
How do you compute addition of two bits?
XOR for the output, MAJ for the carry
What is LOOKUP k?
The length of the array being searched is 2^k
If you have an array of size J, how many lines of code do you need to find elements of the array?
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
How do you update T variables?
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
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?
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
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?
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
If you have an S-bit program representation of a function, how many lines of code does it take to compute evaluate?
O(S^2) (see proof for s line program where S=slogs)
