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

page 9, line 11:

... see Problem 1.4.1 [1.4.11] ...

page 30, line 15:

... we cabn [can] achieve quadratic ...

page 33, line -10:

of the symbols) by $m |\Sigma|^{3ms}$ [$m |\Sigma|^{3mk}$] is some ...

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 185, line -10:

... under complement ([Corollary of] Theorem 7.6), ...

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 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 228, line -1:

... or $2^{n-2} +f 2^{n-3}$ [$2^{n-1} +f 2^{n-2}$

page 246, line 3:

... (see Problem 11.5.6 [11.5.5]

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 264, line 20:

because [our] the hypothetical

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 305, line -18:

inequality $d_{ij} + d_{jk} [\leq] \geq d_{ik}

page 306, line -11:

... generality that [that] ...

page 308, line 1:

Note that $k$ is used here to denote two different integers

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