Modeling running time

[paulaleyes14]

Chapter name: Modeling running time.

List of bugs/typos

1. The section containing the typo is Oblivious NAND-TM programs. It is at the very end of the section, after the sentence "Theorem $13.13$ implies theorem $13.12$" and before the sentence "In the $j$-th copy we replace all references of the form Foo[i] to foo_$i_j$ where $i_j$ is the value of $i$ in the $j$-th iteration". The textbook says that if $P$ is a $k$-line oblivious NAND-TM program computing $F$ in time $T(n)$ then for every $n$ we can obtain a NAND-CIRC program of $(k-1)\cdot T(n)$ lines by simply making $T(n)$ copies of $P$. I think we should rather make something like $T(n)/(k-1)$ copies of $P$, as the fact that $P$ computes $F$ in time $T(n)$ implies that $P$ halts after executing at most $T(n)$ lines, not after executing the loop within $P$ at most $T(n)$ times.