Back
to Topic 8
Language Theory classifies languages (i.e.sets
of words) by their structural complexity.
Thus, regular languages are regarded as simpler than context free languages,
because the FSA has less complex structure than the PDS.
Another classification, called computational
complexity, is based on the amount of resource needed to recognise
a language on some universal computing device, such as a Turing Machine.
The resource in question could be
Consider an off-line Turing Machine,
M, with a read-only input tape, on which the input string is contained
between a pair of distinguished symbols called end markers, and with
k semi-infinite storage tapes.
If we can find a function f: NAT -> NAT, such that, for every input
word of length n, M scans at most f(n) cells
on any storage tape, then M is said to be a f(n) space-bounded
TM.
The language recognised by M is said to be of space complexity f(n).
Note that this definition lets us consider space bounds that are less than linear, that is, where the number of cells used on the storage tapes (not including those on the input tape) is less than the length of the input string.
Consider the language L = {wcw-1| w in (0+1)*}
L is of time complexity n+1 because
L can be recognised by a 2-tape TM, M1, that copies the input to the left of the c onto the second tape.
When a c is found, it moves its second tape head to the left, through the string it has just copied, while it moves its input tape head to the right, comparing the symbols under the two tape heads as they move.
If all the pairs of symbols match, and the number of symbols to the left and right of the c are equal, then M1 accepts.
M1 clearly makes n+1 moves when its input is of length n.
Consider a multitape Turing Machine,
M, with k two-way infinite tapes, one of which contains the input
string and all of which may be written to.
If we can find a function f: NAT -> NAT, such that, for every input
word of length n, M makes at most f(n) moves
before halting, then M is said to be a f(n) time-bounded
TM.
The language recognised by M is said to be of time complexity f(n).
Consider the language L = {wcw-1| w in (0+1)*} again.
L is of space compexity log2n because
L can (also) be recognised by an off-line TM, M2, that uses two storage tapes for binary counters.
First the input tape is checked to see that only one c appears and that there are equal number of symbols to its right and left.
Then the words to the right and left of the c are compared symbol by symbol, using the counters to find corresponding symbols and if they all match, M2 accepts.
The longest string that has to be scanned on either storage tape is the binary representation of the highest counter value.
This value is clearly n and its binary representation is of length log2n.
These measures of space and time bounds
apply equally well to nondeterministic TMs.
A nondeterministic TM is of time complexity f(n) if no sequence
of choices of move on an input of length n causes the machine to make
more than f(n) moves.
It is of space complexity f(n) if no sequence of choices leads
it to scan more than f(n) cells on any storage tape.
We can now define four families of languages by the complexities of the machines that can recognise them, thus:
DSPACE(f(n) ): the set of all languages of space complexity f(n);
NSPACE(f(n) ): those of nondeterministic space complexity f(n);
DTIME(f(n) ): those of time complexity f(n); and
NTIME(f(n) ): those of nondeterministic time complexity f(n).
We have already established relations among the sets of languages recognisable by the various classes of machine, those recognisable by FSAs (the regular languages) being a subset of those recognisable by the PDAs (the context free languages), which are themselves a subset of those recognisable by the TMs (the recursively enumerable languages).
Are there similar relations among the complexity
classes?
We can approach this question by considering the effects on complexity of simulating
of one machine by another.
First, note that the TMs may have arbitrarily
large numbers of states and alphabetic symbols.
By choosing suitable encodings for sets of symbols, we can therefore compress
the amount of space required to recognise a language by a constant
factor.
If a language L is in DSPACE(f(n) ) then it is in DSPACE(cf(n) ) for any constant c>0.
Let M1 be an f(n)-bounded off-line TM that accepts the language L.
We construct a new TM, M2, that simulates M1 where, for some constant, r, each storage cell of M2 holds a symbol representing the contents of r adjacent sells of M1's storage tape. We design M2 so that it keeps track (by suitable changes of state) of which cell M1 is actually scanning.
Then M2 can simulate M1, on an input string of length n,using no more than f(n)/r cells.
If f(n) < r, for all n, then M2 can store in one cell the contents of any tape, so M2 uses only one cell in recognising any string.
If f(n) * r, and rc * 2 for some c>0, then f(n)/r ¾ cf(n).
Expressed in terms of sets of languages, we have:
DSPACE(f(n) ) = DSPACE(cf(n) ) for any constant c>0.
This proof can easily be extended to nondeterministic TMs:
NSPACE(f(n) ) = NSPACE(cf(n) ) for any constant c>0.
If f(n) is not a constant multiple of n (that is, f(n) = kn for some k>0), then
if a language L is in DTIME(f(n) ) then it is in DTIME(cf(n) ) for any constant c>0.
The proof of this theorem also relies on
the construction of a simulator, M2, that encodes r
symbols into one.
M2 can be constructed in such a way that it takes
no more than 8 steps to process each of its encoded symbols (the price
being paid for this being an increase in the number of states it needs to remember
where it is in that cycle).
Since M1 must take at least r steps to process the
string encoded by each such symbol, M2 simulates f(n)
moves of M1 in at most 8f(n)/r moves.
Before starting this simulation, M2 must encode its n
input cells into n/r cells on one of its storage tapes and
return to the left end of this tape, which takes n+n/r
moves.
The total number of moves taken by M2 on an input string of
length n is therefore
n + n/r + 8f(n)/r.
Now, if f(n) is not a constant
multiple of n, we can always find a constant d such that n
¾ f(n)/d.
Given this value, the upper bound on the number of moves taken by M2,
on an input string of length n, is
[1/d + 1/rd + 8/d]f(n)
and we may choose r to make this
number as small as we like, no matter what value d has.
Therefore, for any constant c>0, and any TM, M1,
in DTIME(f(n)), we can design a TM, M2, that
simulates it and is in DTIME(cf(n)). That is:
If f(n) is not a constant multiple of n , then DTIME(f(n) ) = DTIME(cf(n) ) for every constant c>0.
Again, this proof can be extended to nondeterministic TMs:
If f(n) is not a constant multiple of n , then NTIME(f(n) ) = NTIME(cf(n) ) for every constant c>0.
Remember that any TM, M1,
with k tapes, that recognises a language L, can be simulated by
a TM, M2, with a single tape, simply by dividing the
storage tape of M2 into segments, separated by distinguished
symbols.
The number of cells used by M2 in recognising any string of
L is no greater than the number of cells used by M1.
Therefore:
if M1 is any off-line TM, with k storage tapes, of space complexity f(n), then we can construct an off-line TM M2, with one storage tape, that has the same space complexity.
For all space complexity results, therefore,
we may assume that any f(n)-bounded TM has only one storage tape.
In fact, if f(n) > n, the same results are obtained
for single tape TMs as for off-line TMs with one storage tape.
The effects of reduction in the number of tapes on time complexity are slightly more complicated.
The linear tape compression and linear
speed-up theorems show if a language's complexity is bounded by any function
f(n), then it is also bounded by cf(n) for every
constant n.
In other words, multiplication by a constant does not change the complexity
class. It can be shown that this is true also for addition of any constant,
or indeed of any function that grows at a lower rate than f(n).
We therefore refer to complexity classes by the order of their upper
bound functions rather than the functions themselves.
Thus, we write
Of(n)
to refer to all functions of the form cf(n),
or f(n) + k, where c and k are arbitrary
constants, or even f(n) + g(n), where g is
a function that grows more slowly than f as n tends to infinity.
This makes it very clear that the main issue in assigning a language to a complexity
class is the rate of growth in demand for the appropriate resource (space,
time etc.) exhibited by the recognising machine as the length of the input
increases.
Although the lower order factors can make a significant difference at low values
of n, they pale into insignificance as n gets large, as can be
seen from the following (approximate) table:
| log2n | *n | n | nlog2n | n3/2 | n2 | n3 | 2n |
| 3 | 3 | 10 | 30 | 30 | 100 | 1,000 | 1,000 |
| 6 | 10 | 100 | 600 | 1,000 | 10,000 | 1,000,000 | 1030 |
| 9 | 31 | 1,000 | 9,000 | 31,000 | 1,000,000 | 1,000,000,000 | 10301 |
| 13 | 200 | 10,000 | 130,000 | 1,000,000 | 100,000,000 | 1012 | astronomic |
| 16 | 316 | 100,000 | 1,6000,000 | 25,600,000 | 1010 | 1015 | unimaginable |
| 19 | 1,000 | 1,000,000 | 19,000,000 | 361,000,000 | 1012 | 1018 | forget it |
These considerations about the complexity
of the languages recognised by TMs also apply to the complexity of the functions
that they compute.
The resources whose usage we consider in TMs are time, as measured by the number
of moves required, and space, as measured by the number of cells visited.
Programs can compute no more functions than TMs can and they make similar demands
on the resources of the computers they run on: time, as measured by the number
of instructions (of various kinds) that they execute, and space, as measured
by the number of memory locations (of various word lengths) that they consume.
We should therefore expect to find
This is indeed the case.
The main influence on the complexity class of a program is its algorithm.
Most algorithms have a primary parameter, n, which affects the running
time, or memory consumption, most significantly.
This might be the size of a file to be sorted or searched, or the number of
nodes of a graph to be traversed, or the degree of a polynomial to be computed,
etc.
Here are some examples of algorithms of different complexity classes:
If you have comments or
suggestions, email to author at b.cohen@city.ac.uk
or me Vid-Com-Ram
/ members.tripod.com/bummerang
หมายเหตุ : เอกสารเวปหน้านี้นำมาจากมหาวิทยาลัยแห่งหนึ่งในประเทศอังกฤษ
เป็นหลักสูตรคล้ายคลึงกับ CT313 นำมาเพื่อเป็นเอกสารเปรียบเทียบและอ้างอิง มิได้หวังผลประโยชน์ใดๆ
และขอบอกว่าเค้ามีลิขสิทธิ์นะ
Next
Topic
Start
of Module