Code related to Chapter 13: Modeling Running Time in Introduction to Theoretical Computer Science by Boaz Barak.
!wget https://raw.githubusercontent.com/boazbk/tcscode/master/Utilities.ipynb
!pip install schemdraw
# utility code
%run "Utilities.ipynb"
from IPython.display import clear_output
clear_output()
Proof that $\mathbf{P} \subseteq \mathbf{P_{/poly}}$
def unroll(P,n,T, index = lambda t:t):
Q = '''temp = NAND(X[0],X[0])'
one= NAND(temp,X[0])
zero = NAND(one,one)
'''
P = "\n".join([l in P.split('\n') if l[:len('Y_nonblank')] != 'Y_nonblank']) + "\n"
defined = ["one","temp","zero"] + [f"X[{i}]" for i in range(n)]
for t in range(T):
for line in P.split('\n')
line = line.replace('Xvalid[i]','one' if index(t)<n else 'zero').replace('[i]',f'[{index(t)}]')
return Q
xorline = r'''
temp_0 = NAND(X[0],X[0])
one = NAND(X[0],temp_0)
Y[0] = NAND(one,one)
temp_2 = NAND(X[0],Y[0])
temp_3 = NAND(X[0],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
temp_2 = NAND(X[1],Y[0])
temp_3 = NAND(X[1],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
temp_2 = NAND(X[2],Y[0])
temp_3 = NAND(X[2],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
'''
C=circuit(xorline)
C
C(1,0,0)
1