Information Technology Reference
In-Depth Information
Although algorithms with linear or quadratic time bounds are desirable in practice,
polynomial time computation is theoretically satisfactory for several reasons. First,
it rules out exhaustive search solutions which are typically exponential time. Also,
since polynomials are closed under composition, it makes polynomial-time bounded
computation closed under procedure calls. Thus, a polynomial-time bounded pro-
gram making calls to a library of polynomial-time subroutines is still polynomial
time. Furthermore, as reasonable models of computation can simulate each other
with at most a polynomial-time slowdown,
1
it makes the notion of polynomial-time
solvability independent of the computation model.
The next big step was the pioneering research of Cook [
Coo71
], Levin [
Lev73
],
and Karp [
Kar72
]. The class NP, consisting of decision problems that have non-
deterministic polynomial-time decision procedures, was identified as the class that
captures most natural optimization problems of interest. The notion of polynomial-
time reductions was used to compare the relative difficulty of problems. Propositional
formula satisfiability was shown to be NP-complete under polynomial-time reduc-
tions [
Coo71
,
Lev73
]. Then several decision problems, arising from optimization
problems, were shown NP-complete [
Kar72
]. NP-complete problems are the hardest
problems in the class NP as opposed to decision problems that are polynomial-time
solvable.
Let
ˇ
denote a fixed finite alphabet
|
ˇ
|≥
2. Input instances of decision problems
ˇ
∗
comprises of all input instances for a
are encoded as finite strings over
ˇ
. Thus,
ↆ
ˇ
∗
forma language. Therefore, we can
identify decision problems with languages and we use the terms interchangeably. As
is customary in computation theory, we will use the standard Turing machine model
as the model of computation (see e.g. [
HU79
]).
Definition 1.1
Let
A
decision problemand the “yes” instances
A
ↆ
ˇ
∗
be languages.
1. Then
A
is said to be polynomial-time
many-one reducible
to
B
, denoted
A
,
B
p
m
B
,
≤
∈
ˇ
∗
if there is a polynomial-time computable function
f
such that for all
x
x
∈
A
if and only if
f
(
x
)
∈
B
.
2. More generally,
A
is said to be polynomial-time
Turing reducible
to
B
if there is
a polynomial-time bounded oracle Turing machine
M
such that
M
B
accepts the
language
A
.
A language
L
ↆ
ˇ
∗
is in the complexity class P if there is a polynomial-time
bounded deterministic Turing machine (equivalently, a polynomial-time algorithm)
for checking membership in
L
.
A language
L
ↆ
ˇ
∗
is in the complexity class NP if there is a language
A
∈
P
∈
ˇ
∗
and a polynomial
p
such that for all
x
∈
ˇ
≤
p
(
|
x
|
)
:
x
∈
L
if and only if
∃
y
x
,
y
∈
A
,
1
This is a polynomial-time version of the Church-Turing thesis known as the feasibility thesis
[
vEB90
].
