Computational Complexity – Sanjeev Arora

Two views of the PCP Theorem. Proof view Hardness of approximation view PCP verifier (V) ←→ CSP instance (ϕ) PCP proof (π) ←→ Assignment to variables (u) Length of proof ←→ Number of variables (n) Number of queries (q) ←→ Arity of constraints (q) Number of random bits (r) ←→ Logarithm of number of constraints (log m) Soundness parameter (typically 1/2) ←→ Maximum of val(ϕ) for a NO instance Theorem 11.5 (NP ⊆PCP(log n, 1)) ←→ Theorem 11.14 (ρ-GAPqCSP is NP-hard) , Theorem 11.9 (MAX-3SAT is NP-hard to ρ-approximate) while if x̸ ∈L, it will accept with probability at most ρ.

The soundness can be boosted to 1/2 at the expense of a constant factor in the randomness and number of queries (see Exercise 11.1). ■ Theorem 11.9 is equivalent to Theorem 11.14 Since 3CNF formulas are a special case of 3CSP instances, Theorem 11.9 implies Theorem 11.14. We now show the other direction.

Let ϵ > 0 and q ∈N be such that by Theorem 11.14, (1 −ϵ)-GAPqCSP is NP-hard. Let ϕ be a qCSP instance over n variables with m constraints. Each constraint ϕi of ϕ can be expressed as an AND of at most 2q clauses, where each clause is the OR of at most q variables or their negations. Let ϕ′ denote the collection of at most m2q clauses corresponding to all the constraints of ϕ. If ϕ is a YES instance of (1−ϵ)-GAPqCSP (i.e., it is satisfiable), then there exists an assignment satisfying all the clauses of ϕ′.

If ϕ is a NO instance of (1−ϵ)-GAPqCSP, then every assignment violates at least an ϵ fraction of the constraints of ϕ and hence violates at least an ϵ 2q fraction of the constraints of ϕ′. We can use the Cook-Levin technique of Chapter 2 (Theorem 2.10), to transform any clause C on q variables u1, . . . , uq to a set C1, . . .

This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars.

More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, inter- active proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complex- ity, constant depth, algebraic and monotone circuits, proof complexity), average-casecomplexityandhardnessamplification, derandomizationand pseudorandom constructions, and the PCP Theorem.

Sanjeev Arora is a professor in the department of computer science at Princeton University. He has done foundational work on probabilistically checkable proofs and approximability of NP-hard problems. He is the founding director of the Center for Computational Intractability, which is funded by the National Science Foundation. Boaz Barak is an assistant professor in the department of computer science at Princeton University. He has done foundational work in computational complexity and cryptography, especially in developing “non-blackbox” techniques. COMPUTATIONAL COMPLEXITY A Modern Approach SANJEEV ARORA Princeton University BOAZ BARAK Princeton University CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK First published in print format ISBN-13 978-0-521-42426-4 ISBN-13 978-0-511-53381-5 © Sanjeev Arora and Boaz Barak 2009 2007 Information on this title: www.cambridge.org/9780521424264 This publication is in copyright.

Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

Published in the United States of America by Cambridge University Press, New York www.cambridge.org eBook (EBL) hardback To our wives—Silvia and Ravit Contents About this book page xiii Acknowledgments xvii Introduction xix 0 Notational conventions . . . . . . . . . .

. . . . . . . . . . . . . . . . . 1 0.1 Representing objects as strings 2 0.2 Decision problems/languages 3 0.3 Big-oh notation 3 exercises 4 PART ONE: BASIC COMPLEXITY CLASSES 7 1 The computational model—and why it doesn’t matter . . . . . .

. . . .

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 7463f31049c6d8cb
• File Extension: .pdf
• File Size: 4,264,379 bytes (4.067 MB)
• Title: –
• Author: Unknown
• ISBN: 9780521424264, 9780511533815
• Pages: 606
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 1388.22 minutes
• Total Words: 277,645
• Total Characters: 1,555,736
• Average Words per Page: 458.16
• Average Characters per Page: 2567.22

Most Frequent Words

every (1298), theorem (1053), proof (934), function (897), see (722), one (716), algorithm (716), complexity (642), random (625), time (603), number (597), show (584), input (582), probability (580), using (559), polynomial (557), set (543), problem (538), prove (535), since (507), log (506), also (502), let (501), size (493), definition (480), two (479), graph (479), circuit (478), use (476), chapter (463), lemma (461), following (430), section (393), thus (380), lower (368), functions (363), quantum (354), least (353), variables (346), problems (341), computation (340), language (337), first (336), sat (335), given (324), case (320), machine (310), note (310), string (308), bits (305), exists (298), fact (292), polynomial-time (284), output (283), formula (277), example (276), now (274), bounds (269), poly (268), exercise (263), matrix (261), algorithms (260), constant (256), circuits (249), bound (248), say (247), many (246), hence (246), pcp (245), computational (244), inputs (244), boolean (243), verifier (242), even (241), turing (237), class (235), used (230), length (227), proofs (226), probabilistic (224), between (220), define (219), assignment (218), tape (215), compute (212), distribution (210), bit (209), space (205), value (205), defined (203), theory (202), pseudorandom (202), state (200), vertices (194), computing (190), hard (190), variable (187), reduction (187), model (186), result (185).

PDF Download