- page 9, line 11:
- ... see Problem 1.4.1 [1.4.11] ...
- page 29, line 12:
- the subscript s should be k, i.e., ...,w_k, u_k)
- page 30, line 13:
- ... establishing [the] that the palindromes are ...
- page 30, line 15:
- ... we cabn [can] achieve quadratic ...
- page 30, line -16:
- ... we let $\Sigma' = \Sigma \cup \underline{\Sigma} \cup \{\rhd', \lhd, \lhd'\}$ (\lhd' was missing)
- page 33, line -10:
- of the symbols) by $m |\Sigma|^{3ms}$ [$m |\Sigma|^{3mk}$] is some ...
- page 34, line 11:
- (s, \triangleright, \epsilon [x], ...
- page 35, line 6:
- ... output is an [an] ordinary ...
- page 35, line 8:
- ... Whenever $\delta(q,\sigma_1,\ldots,\sigma_k) = $ ... (superscript s should be k)
- page 48, line -5:
- the subscript s should be k, i.e., ...,w_k, u_k; s should be k also in the following sum.
- page 61, line 2:
- ... the object of Problem 8.4.1 [3.4.1] ...
- page 61, line 16:
- This is [is] a consequence ...
- page 61, line 20:
- ... (Proposition 3.2 [3.3]) ....
- page 62, line 20:
- ... accepting lanuage [language] $L$ ....
- page 74, line 18:
- ... if [either] $T \models \phi_1$ or ... ('either' should be removed).
- page 75, line 6:
- in formula (8) the last subscript should be 2 (and not 3).
- page 75, line 7:
- in formula (9) the last subscript should be 2 (and not 3).
- page 77, line 4:
- in the formula $\phi$ the last x_1 and the preceding $\lor$ should be swapped.
- page 80, line -8:
- Formula $\phi$ does not seem to correspond to the circuit in Figure 4.2 (a).
- page 82, line 5:
- Figure 4.3 [4.2]
- page 144, line 7:
- ... has at most [least] four strings;
- page 144, line -4:
- ... linear speedup theorem (Theorem 2.1 [2.2]).
- page 147, line 4:
- ... SPACE([(]f(n))
- page 148, line 9:
- ... is at most $n c_1^{f(n)} = [\leq] c_1^{\log n + f(n)}$
- page 151, line 15:
- Such [a] machine observes ...
- page 153, line 4:
- if $f[(n)] \geq \log n$ is a proper ...
- page 153, line 6:
- Suppose $L \in NSPACE{f(n)}$, [is] decided by an ...
- page 153, line 9:
- in the proof of Theorem 7.5 [7.6] on the ...
- page 153, line 14:
- if $|S(n-1)|$ is computed ... [This $n$ here is the number of nodes in the configuration graph, not the length of the input].
- page 159, line 3:
- (Recall Section 4.3 [4.2] ...
- page 163, line 8:
- ... and of $h_{ijk}$ [$g_{ijk}$]
- page 167, line -17:
- this holds for $|x| \geq 2$ [$x \geq 2$]
- page 168, line 7:
- The folowing [following]
- page 169, line -2:
- ... - 1 [- 2] (see ...
- page 171, line -1:
- $... \in \{0,1\}^{|x|^{k-1}}$ [\{0,1\}^{|x|^{k}-1}]
- page 183, line -6:
- ... each [each] variable is ...
- page 184, line 18:
- ... in the sense of Proposition 9.2 [9.3] ...
- page 184, line 23:
- $\neg \alpha$ must be understood as the complement of $\alpha$, e.g., $\neg\neg \alpha$ means $\alpha$.
- page 185, line -10:
- ... under complement ([Corollary of] Theorem 7.6), we need to [to] ...
- page 186, line -14:
- So, asume [assume] that all ...
- page 202, line 12:
- ... total weight is at most $G$ [$W$] .
- page 203, line 1:
- ... add up to $K = 2^n -1$ [$K = 2^{3m} - 1$]
- page 203, line 22:
- ... To start, $V(w,0) = 0$ for all w. [This does not work, e.g. $V(0,1) = v_1$.]
- page 220, line 23:
- ... see [10].10.4.4
- page 221, line -7:
- ... (see Figure 1.2 [1.4]
- page 221, line -2:
- ... disconnects d [t] from s.
- page 222, line 1:
- ... of capacity K+1 [K-1]
- page 223, line 12:
- ... hust [just] ...
- page 228, line -1:
- ... or $2^{n-2} + 2^{n-3}$ [$2^{n-1} + 2^{n-2}$]
- page 244, line -6:
- ... of telling whether [the determinant of ] a symbolic matrix is ...
- page 246, line 3:
- ... (see Problem 11.5.6 [11.5.5]
- page 247, line 3:
- $x_1$ [$x(1)$]-equation for $x_2$ [$x(2)$] we get ...
- page 252, line 4:
- ... modulo the larger [smaller] one, ...
- page 257, lines -2/-1, page 258 line 3:
- "1" should be replaced by "1/2"
- page 260, line -10:
- length 2/(1-c) [2n/(1-c)]
- page 264, line 20:
- because [our] the hypothetical
- page 269, line 13:
- proof of Proposition 11.6 [11.2]
- page 280, line 4:
- $D([d]e, E(e,x)) = x$ ...
- page 282, line 6:
- Suppose that $[d] e$ is a number ...
- page 284, lines 5/6:
- integer in part [(ii)] (i) of Definition ...
- page 286, lines 11:
- from $(x^e \bmod pq, pq, e)$ ...
- page 288, line -16:
- E([d_{Alice}] e_{Alice}, D(....
- page 289, line 4:
- ... to Alice but not [not] known
- page 292, line 19:
- ... according the [the jth] ith
- page 301, line 2:
- where n is [the of] the
- page 305, line -18:
- inequality $d_{ij} + d_{jk} [\leq] \geq d_{ik}
- page 306, line :
- We start with $W(0,v) = \infty$ for all i and v [Does not work, e.g., $W(1,v) = \infty$ for all $v$. To fix the problem one could define $W(0,0) = 0$. ]
- page 306, line -11:
- ... generality that [that] ...
- page 308, line 1:
- Note that $k$ is used here to denote two different integers
- page 308, line -6:
- to Theorem 9.3 [9.4]
- page 310, line -8:
- and $OPT(R(x)) \leq [\alpha] \alpha' OPT(R'(R(x)))$, ...
- page 311, line 9:
- the second $x$ in the first numerator should be $c$.
- page 314, line 18:
- ... by [defintion] definition can be ...
- page 318, line 12:
- ... the references in [13.4.11] 13.4.12:
- page 318, line -2:
- values are [lineraly] linearly
- page 369, line -5:
- proof of Proposition 11.6 [11.2]
- page 374, line -14:
- paitr [pair] in R
- page 377, line -3:
- see problem 15.5.4 [15.5.14]
- page 414, line -10:
- ... have distance 4 [3].
- page 415, line -11:
- ... recall Section 12.2 [12.1]
- page 428, line 3:
- ... is it true that for all [some] partial truth assignment ... (all/some should be swapped to match the formula on line 8)
- page 429, line 8:
- ... starting fron [from] the ...
- page 449, line -8:
- ... if $i \in S$ [$x_i \in S$], and ... $i \not\in S$ [$x_i \not\in S$]
- page 461, Figure 19:
- Note that there is a missing node and edge after the last "choice gadget".