294 COMPUTATIONAL COMPLEXITY
From the Extended Church-Turing Thesis, we see that these complexity
classes are model-independent. Among these complexity classes, the class P
is the most interesting one. We say a DTM M is a polynomial-time DTM if
M has a time bound t(n) for some polynomial function t(n) = nc. We note
that the composition of two polynomial functions is still a polynomial func-
tion. Therefore, if we have two polynomial-time DTM’s Ml and M2, then the
composition M of these two DTM’s, in the sense that M first simulates Mz
on the input x and then simulates Ml using the output y of Mz as the input,
is also a polynomial-time DTM. Therefore, the class P is closed under compo-
sition (of the polynomial-time machines). In addition, the class P is a robust
class of languages, closed under the language operations union, intersection
and complementation (see Exercise 3 of this section).
Based on the above observations and the empirical studies, people in gen-
eral agree that the class P represents the class of feasibly solvable languages,
or simply feasible problems. The following examples show that P is also closed
under concatenation and the Kleene-star operation.
Example 6.13 Show that if A, B E P, then AB E P.
Proof. Assume that A is accepted by a multi-tape DTM Ml with time bound
pi(n), and B is accepted by a multi-tape DTM M2 with time bound pz(n),
where p1 and p2 are two polynomial functions. Consider an input x, with
I I X = n, to the problem AB. For each partition of x into two substrings
X = 21x2, we check whether x1 E A and x2 e B. We note that checking for
each partition requires time at most
PdlXll) + Pz(lX21) + cn <Pi(n) _ +pz(n) +cn
for some constant c. (The term cn comes from the bookkeepping work to
set up the partition for the machine to perform simulations on Mu and
Mz(x,).) Since there are only n + 1 such partitions, the total computation
time is < - (n + l)(pl(n) + pa(n) + cn), which is a polynomial function. 0Example 6.14 Show that if A E P, then A* E P.
Proof. Assume that A is accepted by a DTM Ml with time bound pl (n) for
some polynomial pl. For each input x, with 1x1 =n>O,xfA ifandonly
if there is a partition of x into nonempty substrings x = 1~11x2 l l l x~, with
1 < - nz - < n, such that xi is in A, for all i = 1,2,... , m.. Note that if we try
all such partitions, our algorithm would take an exponential amount of time,
since there are 2+l such partitions.
So, how do we solve this problem in polynomial time? We note that x has
at most n(n + 1)/2 nonempty substrings. Therefore, even though x has an
exponential number of partitions, some substrings occur in many partitions.
This observation suggests us to use the technique of dynamic programming to
attack the problem A. More precisely, we note that a string x is in A* if and
only if