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)
