List of Corrections - Second Edition 

Page 83, lines 10,11,13:
A third ")" should be added at the end of "DTIME(O(T(n))". 

Page 83, line 12:
A third ")" should be added at the end of "DSPACE(O(S(n))", "NTIME(O(T(n))" and "NSPACE(O(S(n))".

Page 108, line -4:
"than" should be "that".

Page 115, line -14:                   
The "inf" symbol is incorrectly typeset and should appear as on line -15. 

Page 213, line 8:
In Homework 9.3 the hypothesis of the implication is false, so this can be 
proved by showing that this is the case. 

Page 244, line 14:
"u_n" should be "u_{p(n)}". 

Page 244, line -10:
Before the word "Let", add the sentence "Fix this value of j."

Page 256, line 18:                                                                                         
The definition of the set C should start with a "{".

Page 256, line 18:
In the definition of the set C, the exponent of SIGMA should be 
"p(|x|)" and not "(p(|x|)". 

Page 263, line -15: "Widgerson" should be "Wigderson". 

Page 268, line 1:
The two words "a function" should be omitted.

Page 272, line -6:
In the equation at the end of the line, "r_1" should be "r_i". 
Page 276, line 9:
"just we reasoned above" should be "just as we reasoned above".                   

Page 276, line -9:
"Boolean circuits" should be "Boolean values". 

Page 280, line -11: "Ry" should be "Rx". 

Page 295, line -14: "Presberger" should be "Presburger".

Page 293, line   : "HITTING SET" should be "HITTING SET 143".