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.

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 “” is a string over symbols 3, 4, 5, , and . Thus, to describe a string, we must specify the set of symbols to occur in that ...

Start Free Trial

No credit card required