Information Technology Reference
In-Depth Information
Chapter 1
Complexity Theory Basics: NP and NL
Vikraman Arvind
Abstract
We introduce basic concepts and results in computational complexity as
background for some of the articles in this volume. Our focus is on the complex-
ity classes nondeterministic polynomial time (NP) and nondeterministic logarithmic
space (NL). The presentation is aimed at computer science students at a senior under-
graduate level, and assumes some familiarity with algorithm design and theory of
computation. The material is covered at a fairly brisk pace. Several results and proof
details are incorporated in exercises which the reader is urged to solve or look up in
textbooks such as [
BDG88
,
Pap94
,
AB09
].
·
·
Keywords
Nondeterministic polynomial time
NP-completeness
Nondetermin-
istic logarithmic space
Mathematics Subject Classification (2010)
Primary 68Q15.
1.1 NP-completeness
The story of modern computational complexity begins with the advent of stored
program computers in the 1940s and the need for efficiently solving optimization
problems by programming the computer. It was soon discovered that a brute-force
enumerative search for the optimal solution yields only algorithms that take expo-
nential time, since the number of candidate solutions for optimization problems
is typically exponential in the input size. Such solutions were not practical even
for inputs of moderate size. Cobham [
Cob64
] and Edmonds [
Edm65
], around 1965,
independently suggested polynomial-time boundedness as an appropriate theoretical
criterion for efficient computation. This was an important conceptual contribution.
