From christos@cs.ucsd.edu Wed Nov 9 16:52:02 1994 Return-Path: Received: from odin.ucsd.edu by aw.com (5.67b/Spike-2.1) id AA01635; Wed, 9 Nov 1994 16:52:00 -0500 Received: from helios.ucsd.edu by odin.ucsd.edu; id AA07488 sendmail 5.67/UCSDPSEUDO.4-CS via SMTP Wed, 9 Nov 94 13:52:37 -0800 for tstone@aw.com Received: by helios (5.67/UCSDPSEUDO.4) id AA13281 for tstone@aw.com; Wed, 9 Nov 94 13:52:35 -0800 Date: Wed, 9 Nov 94 13:52:35 -0800 From: christos@cs.ucsd.edu (Christos Papadimitriou) Message-Id: <9411092152.AA13281@helios> To: tstone@aw.com Subject: Errata, plain text Status: RO ERRATA FOR COMPUTATIONAL COMPLEXITY by Christos H. Papadimitriou published by Addison-Wesley, 1994 page 29, line 12, (twice): subscripts ``s'' should be ``k'' page 35, line 8: subscript ``s'' should be ``k'' page 75, lines 7 and 7: subscript ``3'' should be ``2'' page 78, line 21: delete second ``and'' page 90, line 13: ``U arrow U sup k'' should be ``U sup k arrow U'' page 92, line -9: ``the form n+i, where n is any integer'' should be ``the form n+mi, where n and m are integers'' page 92, line -6: ``and a complex integer n+i to (n+i)+1'' should be ``and a complex integer n+mi to (n+mi)+1'' page 92, line -5 ``contains now a totally disjoint line.'' should be ``contains now an infinity of parallel lines.'' page 97, line -1: second ``x'' should be ``t'' page 103, line GR4: ``z'' should be ``x'' page 105, line -9: ``phi implies phi sub i'' should be ``for all x phi sub i'' page 110, line -12: first `Delta'' should be ``Delta prime'' page 110, line -11: ``not forall psi'' should be ``not forall x psi'' page 119, lines 15-16 should be: ``show that the first form of the completeness theorem implies the second form'' (not the other way around) page 119, line -2: ``phi['' should be ``phi sup * ['' page 131, line 16: ``u yield u prime'' should be ``u prime yield u'' page 156, line 23: second ``Phi'' should be ``Phi prime'' page 174, line 174 ``(Problem 8.4.13)'' should be ``(Problem 8.4.11)'' page 175, line -11, "T sub ``yes''" should be "T sub not ``no''" page 176, line 17: ``M sup G'' should be ``G sup M'' page 179, line 25: ``1962'' should be ``1982'' page 214, line 4: ``its subgraphs'' should be ``its induced subgraphs'' page 244, line -6: ``whether a'' should be ``whether the determinant of a'' page 248, line 1: ``of 561 pass'' should be ``in Phi(561) pass'' page 258, line -11: ``Bernoulli'' should be ``binomial'' page 260, line -10: numerator ``2'' should be ``n/2'' page 321, lines 8, 13, -1; page 322, line 9: ``MAXSAT'' should be ``MAX3SAT'' page 326, lines 13--17: Delete part (a) of Problem 13.4.9. Rename part (b) to (a), and Part (c) to (b). page 328, line -2: ``Tha'' should be ``The'' page 363, lines 8--9: Delete sentence ``If we need ... work is needed.'' page 381, line -15: ``gates'' should be ``input gates'' page 436, line 15; also, page 521: ``Nielson'' should be ``Nilsson'' page 475, line 9: ``we require of interactive protocols, but never'' should be ``required of interactive protocols, but this never'' page 498, line 2: ``2-NEXP were equal, equality'' should be ``2-NEXP were unequal, inequality'' p. 500, line 8, add this reference (before the two by Book): O. Ibarra ``A note concerning nondeterministic tape complexities'', J.ACM, 19, pp. 608-612, 1972,