ISBN-10:
0521122546
ISBN-13:
9780521122542
Pub. Date:
08/16/2010
Publisher:
Cambridge University Press
P, NP, and NP-Completeness: The Basics of Computational Complexity

P, NP, and NP-Completeness: The Basics of Computational Complexity

by Oded Goldreich

Paperback

View All Available Formats & Editions
Current price is , Original price is $44.99. You
Select a Purchase Option
  • purchase options
    $44.99
  • purchase options

Product Details

ISBN-13: 9780521122542
Publisher: Cambridge University Press
Publication date: 08/16/2010
Pages: 214
Sales rank: 741,221
Product dimensions: 6.00(w) x 8.90(h) x 0.50(d)

About the Author

Oded Goldreich is a Professor of Computer Science at the Weizmann Institute of Science and an incumbent of the Meyer W. Weisgal Professorial Chair. He is an editor for the SIAM Journal on Computing, the Journal of Cryptology, and Computational Complexity and previously authored the books Modern Cryptography, Probabilistic Proofs and Pseudorandomness, the two-volume work Foundations of Cryptography, and Computational Complexity: A Conceptual Perspective.

Table of Contents

List of Figures xi

Preface xiii

Overview xvii

To the Teacher xxi

Notations and Conventions xxv

Main Definitions and Results xxvii

1 Computational Tasks and Models 1

Teaching Notes 2

1.1 Representation 3

1.2 Computational Tasks 5

1.2.1 Search Problems 5

1.2.2 Decision Problems 6

1.2.3 Promise Problems (an Advanced Comment) 8

1.3 Uniform Models (Algorithms) 8

1.3.1 Overview and General Principles 9

1.3.2 A Concrete Model: Turing Machines 11

1.3.2.1 The Actual Model 12

1.3.2.2 The Church-Turing Thesis 16

1.3.3 Uncomputable Functions 18

1.3.3.1 On the Existence of Uncomputable Functions 18

1.3.3.2 The Halting Problem 19

1.3.3.3 A Few More Undecidability Results 21

1.3.4 Universal Algorithms 22

1.3.4.1 The Existence of Universal Algorithms 23

1.3.4.2 A Detour: Kolmogorov Complexity 24

1.3.5 Time (and Space) Complexity 26

1.3.6 Oracle Machines and Turing-Reductions 29

1.3.7 Restricted Models 31

1.4 Non-Uniform Models (Circuits and Advice) 31

1.4.1 Boolean Circuits 32

1.4.1.1 The Basic Model 32

1.4.1.2 Circuit Complexity 35

1.4.2 Machines That Take Advice 36

1.4.3 Restricted Models 37

1.4.3.1 Boolean Formulae 38

1.4.3.2 Other Restricted Classes of Circuits 39

1.5 Complexity Classes 40

Exercises 41

2 The P versus NP Question 48

Teaching Notes 49

2.1 Efficient Computation 50

2.2 The Search Version: Finding versus Checking 53

2.2.1 The Class P as a Natural Class of Search Problems 54

2.2.2 The Class NP as Another Natural Class of Search Problems 56

2.2.3 The P versus NP Question in Terms of Search Problems 57

2.3 The Decision Version: Proving versus Verifying 58

2.3.1 The Class P as a Natural Class of Decision Problems 59

2.3.2 The Class NP and NP-Proof Systems 59

2.3.3 The P versus NP Question in Terms of Decision Problems 62

2.4 Equivalence of the Two Formulations 63

2.5 Technical Comments Regarding NP 65

2.6 The Traditional Definition of NP 66

2.7 In Support of P Being Different from NP 69

2.8 Philosophical Meditations 70

Exercises 71

3 Polynomial-time Reductions 74

Teaching Notes 75

3.1 The General Notion of a Reduction 75

3.1.1 The Actual Formulation 76

3.1.2 Special Cases 77

3.1.3 Terminology and a Brief Discussion 79

3.2 Reducing Optimization Problems to Search Problems 81

3.3 Self-Reducibility of Search Problems 83

3.3.1 Examples 85

3.3.2 Self-Reducibility of NP-Complete Problems 87

3.4 Digest and General Perspective 88

Exercises 89

4 NP-Completeness 96

Teaching Notes 97

4.1 Definitions 98

4.2 The Existence of NP-Complete Problems 99

Bounded Halting and Non-Halting 102

4.3 Some Natural NP-Complete Problems 103

4.3.1 Circuit and Formula Satisfiability: CSAT and SAT 104

4.3.1.1 The NP-Completeness of CSAT 105

4.3.1.2 The NP-Completeness of SAT 109

4.3.2 Combinatorics and Graph Theory 113

4.3.3 Additional Properties of the Standard Reductions 120

4.3.4 On the Negative Application of NP-Completeness 121

4.3.5 Positive Applications of NP-Completeness 122

4.4 NP Sets That Are Neither in P nor NP-Complete 126

4.5 Reflections on Complete Problems 130

Exercises 133

5 Three Relatively Advanced Topics 142

Teaching Notes 142

5.1 Promise Problems 142

5.1.1 Definitions 143

5.1.1.1 Search Problems with a Promise 143

5.1.1.2 Decision Problems with a Promise 144

5.1.1.3 Reducibility Among Promise Problems 145

5.1.2 Application and Limitations 146

5.1.2.1 Formulating Natural Computational Problems 146

5.1.2.2 Restricting a Computational Problem 147

5.1.2.3 Non-generic Applications 147

5.1.2.4 Limitations 148

5.1.3 The Standard Convention of Avoiding Promise Problems 149

5.2 Optimal Search Algorithms for NP 151

5.3 The Class coNP and Its Intersection with NP 154

Exercises 158

Historical Notes 165

Epilogue: A Brief Overview of Complexity Theory 169

Appendix: Some Computational Problems 177

A.1 Graphs 177

A.2 Boolean Formulae 179

Bibliography 181

Index 183

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews