Skip to Main Content
Theory of Computational Complexity, 2nd Edition
book

Theory of Computational Complexity, 2nd Edition

by Ding-Zhu Du, Ker-I Ko
June 2014
Intermediate to advanced content levelIntermediate to advanced
512 pages
17h 55m
English
Wiley
Content preview from Theory of Computational Complexity, 2nd Edition

Chapter 1

Models of Computation and Complexity Classes

O time! thou must untangle this, not I; It is too hard a knot for me to untie.

—William Shakespeare

The greatest friend of truth is time.

—Charles Caleb Colton

The notions of algorithms and complexity are meaningful only when they are defined in terms of formal computational models. In this chapter, we introduce our basic computational models: deterministic Turing machines and nondeterministic Turing machines. Based on these models, we define the notion of time and space complexity and the fundamental complexity classes including P and NP. In the last two sections, we study two best known proof techniques, diagonalization and simulation, that are used to separate and collapse complexity classes, respectively.

1.1 Strings, Coding, and Boolean Functions

Our basic data structure is a string. All other data structures are tobe encoded and represented by strings. A string is a finite sequence of symbols. For instance, the word string is a string over the symbols of English letters; the arithmetic expression “c01-math-0001” is a string over symbols 3, 4, 5, c01-math-0002, and c01-math-0003. Thus, to describe a string, we must specify the set of symbols to occur in that ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Theory of Computation

Theory of Computation

George Tourlakis

Publisher Resources

ISBN: 9781118594971Purchase book