You have reached 400 XP and carrot coins. That is the daily max!

This highly anticipated revision builds upon the strengths of the previous edition. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative "proof idea" sections explain profound concepts in plain English. The new edition incorporates many improvements students and professors have suggested over the years, and offers updated, classroom-tested problem sets at the end of each chapter.

Customers also bought

Book details

List price: $267.95 Edition: 2nd Copyright year: 2006 Publisher: Course Technology Publication date: 2/15/2005 Binding: Hardcover Pages: 400 Size: 6.50" wide x 9.25" long x 1.00" tall Weight: 1.628 Language: English

AuthorTable of Contents

Michael Sipser has taught theoretical computer science and mathematics at the Massachusetts Institute of Technology for the past 32 years. He is a Professor of Applied Mathematics, a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and the current head of the mathematics department. He enjoys teaching and pondering the many mysteries of complexity theory.

Preface to the First Edition

To the student

To the educator

The first edition

Feedback to the author

Acknowledgments

Preface to the Second Edition

Introduction

Automata, Computability, and Complexity

Complexity theory

Computability theory

Automata theory

Mathematical Notions and Terminology

Sets

Sequences and tuples

Functions and relations

Graphs

Strings and languages

Boolean logic

Summary of mathematical terms

Definitions, Theorems, and Proofs

Finding proofs

Types of Proof

Proof by construction

Proof by contradiction

Proof by induction

Exercises, Problems, and Solutions

Automata and Languages

Regular Languages

Finite Automata

Formal definition of a finite automaton

Examples of finite automata

Formal definition of computation

Designing finite automata

The regular operations

Nondeterminism

Formal definition of a nondeterministic finite automaton

Equivalence of NFAs and DFAs

Closure under the regular operations

Regular Expressions

Formal definition of a regular expression

Equivalence with finite automata

Nonregular Languages

The pumping lemma for regular languages

Exercises, Problems, and Solutions

Context-Free Languages

Context-free Grammars

Formal definition of a context-free grammar

Examples of context-free grammars

Designing context-free grammars

Ambiguity

Chomsky normal form

Pushdown Automata

Formal definition of a pushdown automaton

Examples of pushdown automata

Equivalence with context-free grammars

Non-context-free Languages

The pumping lemma for context-free languages

Exercises, Problems, and Solutions

Computability Theory

The Church-Turing Thesis

Turing Machines

Formal definition of a Turing machine

Examples of Turing machines

Variants of Turing Machines

Multitape Turing machines

Nondeterministic Turing machines

Enumerators

Equivalence with other models

The Definition of Algorithm

Hilbert's problems

Terminology for describing Turing machines

Exercises, Problems, and Solutions

Decidability

Decidable Languages

Decidable problems concerning regular languages

Decidable problems concerning context-free languages

The Halting Problem

The diagonalization method

The halting problem is undecidable

A Turing-unrecognizable language

Exercises, Problems, and Solutions

Reducibility

Undecidable Problems from Language Theory

Reductions via computation histories

A Simple Undecidable Problem

Mapping Reducibility

Computable functions

Formal definition of mapping reducibility

Exercises, Problems, and Solutions

Advanced Topics in Computability Theory

The Recursion Theorem

Self-reference

Terminology for the recursion theorem

Applications

Decidability of logical theories

A decidable theory

An undecidable theory

Turing Reducibility

A Definition of Information

Minimal length descriptions

Optimality of the definition

Incompressible strings and randomness

Exercises, Problems, and Solutions

Complexity Theory

Time Complexity

Measuring Complexity

Big-O and small-o notation

Analyzing algorithms

Complexity relationships among models

The Class P

Polynomial time

Examples of problems in P

The Class NP

Examples of problems in NP

The P versus NP question

NP-completeness

Polynomial time reducibility

Definition of NP-completeness

The Cook-Levin Theorem

Additional NP-complete Problems

The vertex cover problem

The Hamiltonian path problem

The subset sum problem

Exercises, Problems, and Solutions

Space Complexity

Savitch's Theorem

The Class PSPACE

PSPACE-completeness

The TQBF problem

Winning strategies for games

Generalized geography

The Classes L and NL

NL-completeness

Searching in graphs

NL equals coNL

Exercises, Problems, and Solutions

Intractability

Hierarchy Theorems

Exponential space completeness

Relativization

Limits of the diagonalization method

Circuit Complexity

Exercises, Problems, and Solutions

Advanced topics in complexity theory

Approximation Algorithms

Probabilistic Algorithms

The class BPP

Primality

Read-once branching programs

Alternation

Alternating time and space

The Polynomial time hierarchy

Interactive Proof Systems

Graph nonisomorphism

Definition of the model

IP = PSPACE

Parallel Computation

Uniform Boolean circuits

The class NC

P-completeness

Cryptography

Secret keys

Public-key cryptosystems

One-way functions

Trapdoor functions

Exercises, Problems, and Solutions

Selected Bibliography

Free shipping

A minimum purchase of $35 is required. Shipping is provided via FedEx SmartPost® and FedEx Express Saver®. Average delivery time is 1 – 5 business days, but is not guaranteed in that timeframe. Also allow 1 - 2 days for processing. Free shipping is eligible only in the continental United States and excludes Hawaii, Alaska and Puerto Rico. FedEx service marks used by permission."Marketplace" orders are not eligible for free or discounted shipping.

Our guarantee

If an item you ordered from TextbookRush does not meet your expectations due to an error on our part, simply fill out a return request and then return it by mail within 30 days of ordering it for a full refund of item cost.