Information Technology Reference
In-Depth Information
σ
(Σ
∗
−
I
)
Encodings of Instances
L
(
P
)
L
(
co
P
)
Figure 8.1
The language
L
(
P
)
of a decision problem
P
and the language of its complement
L
(
co
P
)
.Thelanguages
L
(
P
)
and
L
(
co
P
)
encode all instances of
I
. The complement of
L
(
P
)
,
P
)
with
σ
(Σ
∗
− I
)
, strings that are in neither
L
(
P
)
nor
L
(
co
L
(
P
)
,istheunionof
L
(
co
P
)
.
8.3
Resource Bounds
One of the most important problems in computer science is the identification of the computa-
tionally feasible problems. Currently a problem is considered feasible if its running time on a
DTM (deterministic Turing machine) is polynomial. (Stated by Edmonds [
96
], this is known
as the
serial computation thesis
.) Note, however, that some polynomial running times, such
as
n
1000
,where
n
is the length of a problem instance, can be enormous. In this case doubling
n
increases the time bound by a factor of 2
1000
, which is approximately 10
301
!
Since problems are classified by their use of resources, we need to be precise about
resource
bounds
.Thesearefunctions
r
:
→
from the natural numbers
=
{
0, 1, 2, 3,
...
}
to
the natural numbers. The resource functions used in this chapter are:
r
(
n
)=
O
(log
n
)
Logarithmic function
r
(
n
)=log
O
(
1
)
n
Poly-logarithmic function
r
(
n
)=
O
(
n
)
Linear function
r
(
n
)=
n
O
(
1
)
Polynomial function
r
(
n
)=
2
n
O
(
1
)
Exponential function
A resource function that grows faster than any polynomial is called a
superpolynomial func-
tion
. For example, the function
f
(
n
)=
2
log
2
n
grows faster than any polynomial (the ratio
log
f
(
n
)
/
log
n
is unbounded) but more slowly than any exponential (for any
k>
0theratio
(log
2
n
)
/n
k
becomes vanishingly small with increasing
n
).
Another note of caution is appropriate here when comparing resource functions. Even
though one function,
r
(
n
)
, may grow more slowly asymptotically than another,
s
(
n
)
,itmay
still be true that
r
(
n
)
>s
(
n
)
for very large values of
n
. For example,
r
(
n
)=
10
log
4
n>
s
(
n
)=
n
for
n
1,889,750 despite the fact that
r
(
n
)
is much smaller than
s
(
n
)
for large
n
.
Some resource functions are so complex that they cannot be computed in the time or space
that they define. For this reason we assume throughout this chapter that all resource functions
are proper. (Definitions of time and space on Turing machines are given in Section
8.4.2
.)
≤
DEFINITION
8.3.1
Afunction
r
:
r
(
n
))
and for some tape symbol
a
there is a deterministic multi-tape Turing machine
M
that, on all
→
is
proper
if it is nondecreasing
(
r
(
n
+
1
)
≥
Search WWH ::
Custom Search