Errata to C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994

page 9, line 11:
... see Problem 1.4.1 [1.4.11] ...
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'\}$
page 33, line -10:
of the symbols) by $m |\Sigma|^{3ms}$ [$m |\Sigma|^{3mk}$] is some ...
page 35, line 6:
... output is an [an] ordinary ...
page 35, line 8:
... Whenever $\delta(q,\sigma_1,\ldots,\sigma_k) = $ ...
page 61, line 2:
... the object of Problem 8.4.1 [3.4.1] ...
page 61, line 20:
... (Proposition 3.2 [3.3]) ....
page 62, line 20:
... accepting lanuage [language] $L$ ....
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 168, line 7:
The folowing [following]
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 222, line 1:
... of capacity K+1 [K-1]
page 223, line 12:
... hust [just] ...
page 228, line -1:
... or $2^{n-2} +f 2^{n-3}$ [$2^{n-1} +f 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 258, Corollary:
$\leq$ should be replaced by $\geq$
page 258, Proof of the corollary:
minus sign missing from the expression for $\theta$
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$.]
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$]
Comments to
Ilkka.Niemela@hut.fi