Computability and Complexity : Foundations and Tools for Pursuing Scientific Applications

• Autore: Downey Rod
• Pubblicazione: Cham : , : Springer, , 2024; ©2024
• Edizione: 1st ed.
• Descrizione fisica: 1 online resource (361 pages)
• Nota di contenuto: Intro -- Preface -- Acknowledgements -- Introduction -- Contents -- Part I Background -- Chapter 1 Some Naive Set Theory -- 1.1 Introduction -- 1.1.1 Basic definitions -- 1.1.2 Countable sets -- 1.2 Gödel numberings and other coding techniques -- 1.2.1 Exercises -- 1.3 Diagonalization and Uncountable Sets -- 1.3.1 Exercises -- 1.4 Set Theory in Mathematics -- 1.4.1 The Cardinality of a Set and the Continuum Hypothesis* -- Part II Computability Theory -- Chapter 2 Regular Languages and Finite Automata -- 2.1 Introduction -- 2.2 Regular Languages -- 2.2.1 Formal languages -- 2.2.2 Regular expressions and languages -- 2.2.3 The Pumping Lemma -- 2.2.4 Exercises -- 2.2.5 Closure properties of regular languages -- 2.3 Finite State Automata -- 2.3.1 Deterministic Finite Automata -- 2.4 Exercises -- 2.4.1 Nondeterministic Finite Automata -- 2.4.2 The Rabin-Scott Theorem -- 2.4.3 Exercises -- 2.4.4 Nondeterministic automata with ⋋-moves -- 2.5 Exercises -- 2.6 Kleene's Theorem: Finite State = Regular -- 2.6.1 Historical Notes -- 2.7 The Myhill-Nerode Theorem* -- 2.7.1 The Method of Test Sets -- 2.7.2 State Minimization* -- 2.7.3 Exercises -- 2.7.4 Historical Notes -- Chapter 3 General Models of Computation -- 3.1 Introduction -- 3.2 Turing Machines -- 3.2.1 Exercises -- 3.2.2 Coding, Gödel numbering and other domains beside N -- 3.2.3 Exercises -- 3.2.4 The Church-Turing Thesis -- 3.2.5 Nondeterminism -- 3.2.6 A Universal Turing machine -- 3.3 Partial recursive functions -- 3.3.1 Primitive recursive functions -- 3.3.2 Exercises -- 3.3.3 Primitive Recursive Relations -- 3.3.4 Bounded quantification -- 3.3.5 Exercises -- 3.3.6 Partial recursive functions -- 3.3.7 Gödel Numbering Turing Computations -- 3.3.8 The Kleene Normal Form Theorem -- 3.4 Minsky and Register Machines -- 3.4.1 Exercises -- Chapter 4 Undecidable Problems -- 4.1 Introduction. ; 4.1.1 Exercises -- 4.1.2 The Halting Problem -- 4.1.3 Exercises -- 4.2 Minsky Machines and Generalized Collatz Functions -- 4.2.1 Collatz functions -- 4.2.2 Vector games -- 4.2.3 Rational Games -- 4.2.4 Generalized Collatz functions -- 4.2.5 Exercises -- 4.3 Unsolvable Word problems -- 4.3.1 Semi-Thue Processes -- 4.3.2 Thue Processes and Word Problems in Semigroups -- 4.3.3 Exercises -- 4.3.4 Post's correspondence problem -- 4.3.5 Groups* -- 4.3.6 The Entscheidungsproblem* -- 4.3.7 Diophantine equations* -- 4.3.8 Exercises -- 4.3.9 Coda -- Chapter 5 Deeper Computability -- 5.1 Introduction -- 5.1.1 Computably Enumerable Sets -- 5.1.2 Exercises -- 5.1.3 The s-m-n Theorem -- 5.2 Index Sets and Rice's Theorem -- 5.3 The Recursion Theorem -- 5.3.1 An Alternative Proof of the Recursion Theorem* -- 5.3.2 Exercises -- 5.4 Wait and See Arguments -- 5.4.1 Some Examples -- 5.4.2 Computable Structure Theory: Computable Linear Orderings -- 5.4.3 Exercises -- 5.5 Turing Reducibility -- 5.5.1 Oracle machines and Turing reducibility -- 5.5.2 Universal Oracle Machines -- 5.5.3 Use functions -- 5.5.4 The jump operator -- 5.6 The Arithmetic Hierarchy -- 5.6.1 The Limit Lemma -- 5.6.2 Exercises -- 5.6.3 Post's Theorem -- 5.6.4 Exercises -- 5.7 The Structure of Turing Degrees and Post's Problem -- 5.7.1 Exercises -- 5.7.2 Post's Problem and the Finite Injury Priority Method -- 5.7.3 Exercises -- 5.7.4 Sacks' Splitting Theorem* -- 5.7.5 Exercises -- Part III Computational Complexity Theory -- Chapter 6 Computational Complexity -- 6.1 Introduction -- 6.1.1 Size matters -- 6.1.2 The Basic Model -- 6.1.3 Discussion and Basic Definitions -- 6.1.4 Exercises -- 6.1.5 Polynomial Time and Space -- 6.1.6 Universal Enumerations -- 6.1.7 Using Clocks -- 6.1.8 Hierarchy Theorems -- 6.1.9 Exercises -- 6.2 Blum's Speedup Theorem -- 6.3 The Union Theorem*. ; Chapter 7 NP- and PSPACE-Completeness -- 7.1 The Polynomial Time Hierarchy -- 7.2 NP Completeness -- 7.2.1 Machine NP-Complete Problems -- 7.2.2 Exercises -- 7.2.3 The Cook-Levin Theorem -- 7.2.4 Search vs Decision Problems: Polynomial Time Turing Reductions -- 7.2.5 Exercises -- 7.2.6 Some Natural NP-Complete Problems -- 7.2.7 Exercises -- 7.2.8 More NP-Completeness -- 7.2.9 Exercises -- 7.2.10 Even More NP-Completeness -- 7.2.11 Commentary* -- 7.2.12 Exercises -- 7.3 Space -- 7.3.1 Savitch's Theorem -- 7.3.2 Time vs Space -- 7.3.3 Exercises -- 7.4 Natural PSPACE-Complete Problems -- 7.4.1 Exercises -- 7.5 Further Variations on the Theme : Advice Classes and Randomized Reductions -- 7.5.1 Introduction -- 7.5.2 Advice and Nonuniform Complexity Classes -- 7.5.3 Valiant-Vazirani and BPP -- Chapter 8 Some Structural Complexity -- 8.1 Introduction -- 8.1.1 Oracles -- 8.1.2 Exercises -- 8.1.3 The Role of Oracles and Other Indications that We Don't Know How to Approach P vs NP -- 8.2 Polynomial Time Degrees and Ladner's Theorem -- 8.2.1 Exercises -- Chapter 9 Parameterized Complexity -- 9.1 Introduction -- 9.2 Formal Definitions -- 9.2.1 Discussion -- 9.3 Parametric Intractability -- 9.3.1 A basic hardness class: W[1] -- 9.3.2 Exercises -- 9.3.3 The W-hierarchy -- 9.3.4 Showing Known Algorithms are Likely Very Bad Indeed -- Especially in PTAS's -- 9.4 Parameterized Tractability -- 9.4.1 Bounded Search Trees -- 9.4.2 Exercises -- 9.4.3 Kernelization -- 9.4.4 Exercises -- 9.4.5 Iterative Compression -- 9.4.6 Exercises -- 9.4.7 Not-Quite-Practical FPT Algorithms* -- 9.4.8 Exercises -- 9.5 Kernelization Lower Bounds -- 9.5.1 Exercises -- 9.6 Another Basic Hardness Class and XP Optimality* -- 9.6.1 Exercises -- Chapter 10 Other Approaches to Coping with Hardness* -- 10.1 Introduction -- 10.2 Approximation Algorithms -- 10.2.1 Constant Distance Approximation. ; 10.2.2 Exercises -- 10.2.3 Constant Approximation Ratios -- 10.2.4 APX Completeness -- 10.2.5 Exercises -- 10.2.6 PTAS's -- 10.2.7 Parameterized Approximation -- 10.2.8 Parameterized Inapproximability -- 10.2.9 Exercises -- 10.3 Average Case Complexity -- 10.3.1 Polynomial Time on Average -- 10.3.2 DistNP -- 10.3.3 Livne's ``Natural'' Average Case Complete Problems -- 10.3.4 Exercises -- 10.4 Generic Case Complexity -- 10.4.1 Basic Definitions -- 10.4.2 Exercises -- 10.5 Smoothed Analysis -- 10.6 Summary -- Part IV Selected Solutions to Exercises -- Chapter 11 Solutions -- 11.1 Chapter 1 -- 11.2 Chapter 2 -- 11.3 Chapter 3 -- 11.4 Chapter 5 -- 11.5 Chapter 6 -- 11.6 Chapter 7 -- 11.7 Chapter 8 -- 11.8 Chapter 9 -- 11.9 Chapter 10 -- References -- Index.
• Titolo autorizzato: Computability and Complexity
• ISBN: 3-031-53744-0
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910857794903321
• Lo trovi qui: Univ. Federico II
• Serie: Undergraduate Topics in Computer Science Series