Information Technology Reference
In-Depth Information
space
n
k
, respectively, for
n
the length of the input. Since time and space on a Turing machine
are measured by the number of steps and number of tape cells, it is straightforward to show
that time and space for a given Turing machine, deterministic or not, can each be reduced by
a constant factor by modifying the Turing machine description so that it acts on larger units
of information. (See Problem
8.8
.) Thus, for a constant
K>
0 the following classes are the
same: a)
TIME
(
k
n
)
and
TIME
(
Kk
n
)
,b)
NTIME
(
k
n
)
and
NTIME
(
Kk
n
)
,c)
SPACE
(
n
k
)
and
SPACE
(
Kn
k
)
,andd)
NSPACE
(
n
k
)
and
NSPACE
(
Kn
k
)
.
To emphasize that the union of complexity classes is another complexity class, we define
as unions two of the most important Turing complexity classes,
P
, the class of deterministic
polynomial-time decision problems, and
NP
, the class of nondeterministic polynomial-time
decision problems.
DEFINITION
8.5.2
The classes
P
and
NP
are sets of decision problems solvable in polynomial time
on DTMs and NDTMs, respectively; that is, they are defined as follows:
P
=
k≥
0
TIME
(
n
k
)
NP
=
k≥
NTIME
(
n
k
)
0
in
P
there is a DTM
M
and a polynomial
p
(
n
)
such
that
M
halts on each input string of length
n
in
p
(
n
)
steps, accepting this string if it is an
instance
w
of
Thus, for each decision problem
P
P
and rejecting it otherwise.
Also, for each decision problem
P
in
NP
there is an NDTM
M
and a polynomial
p
(
n
)
such that for each instance
w
of
P
|
w
|
=
n
, there is a choice input of length
p
(
n
)
such that
,
M
accepts
w
in
p
(
n
)
steps.
Problems in
P
are considered
feasible problems
because they can be decided in time poly-
nomial in the length of their input. Even though some polynomial functions, such as
n
1000
,
grow very rapidly in their one parameter, at the present time problems in
P
are considered
feasible. Problems that require exponential time are not considered feasible.
The class
NP
includes the decision problems associated with many hundreds of important
searching and optimization problems, such as
TRAVELING SALESPERSON
described below.
(See Fig.
8.4
.) If
P
is equal to
NP
, then these important problems have feasible solutions. If
not, then there are problems in
NP
that require superpolynomial time and are therefore largely
infeasible. Thus, it is very important to have the answer to the question
P
=
NP
.
TRAVELING SALESPERSON
Instance:
An integer
k
and a set of
n
2
{
d
i
,
j
|
≤
i
,
j
≤
n
}
symmetric integer distances
1
between
n
cities where
d
i
,
j
=
d
j
,
i
.
Answer:
“Yes” if there is a
tour
(an ordering)
{
i
1
,
i
2
,
...
,
i
n
}
of the cities such that the
length
l
=
d
i
1
,
i
2
+
d
i
2
,
i
3
+
···
+
d
i
n
,
i
1
of the tour satisfies
l
≤
k
.
The
TRAVELING SALESPERSON
problem is in
NP
because a tour satisfying
l
≤
k
can
be chosen nondeterministically in
n
steps and the condition
l
k
then verified in a polyno-
mial number of steps by finding the distances between successive cities on the chosen tour in
the description of the problem and adding them together. (See Problem
3.24
.) Many other
important problems are in
NP
, as we see in Section
8.10
. While it is unknown whether a
deterministic polynomial-time algorithm exists for this problem, it can clearly be solved deter-
≤
Search WWH ::
Custom Search