Chapter in the book
Chapter 23: Turing Machines, P and NP Classes, and Other Models of Computation
Published Online on: Oct 04, 2021
Requires Authorization
0
Frontmatter
Contents
Preface
Chapter 1: A Brief Survey of Elementary Functions
Chapter 2: Propositional Algebra
Chapter 3: Naïve and Formal (Axiomatic) Set Theory
Chapter 4: Groups, Rings, and Fields
Chapter 5: Predicates and Quantifiers—Algebraic Theory
Chapter 6: Binary Relations and Relational Databases
Chapter 7: Combinatorics
Chapter 8: Elements of Number Theory
Chapter 9: Boolean Functions
Chapter 10: Hashing Functions and Cryptographic Maps
Chapter 11: Generating Polynomials and Inversion Formulas
Chapter 12: Systems of Representatives
Chapter 13: Boolean Algebras
Chapter 14: Combinatorial Circuits
Chapter 15: Complete Systems of Boolean Functions and Bases
Chapter 16: Introductory Graph Theory, Euler’s Formula, and Unbreakable Ciphers
Chapter 17: Trees and Digraphs
Chapter 18: Computations and Algorithms
Chapter 19: Finite Automata
Chapter 20: Introduction to Game Theory
Chapter 21: Information Theory and Coding
Chapter 22: Probability Theory with a Finite Sample Space and the Birthday Problem
Chapter 23: Turing Machines, P and NP Classes, and Other Models of Computation
Chapter 24: Answers and Solutions to Selected Exercises
Bibliography
Index