University of Sussex Spring 2021 Informatics
Limits of Computation
Exercises 7
Time Bounds, Complexity Classes, Hierarchy Theorems
(Lectures 12-15)
1. Consider the following two WHILE-program p (see also Question 3 on Sheet 6):
p read X {
Y:= cons X X
}
write Y
(a) Give a time bound for p.
(b) In which of the following classes is program p?
i. WHILEtime(2n)
ii. WHILEtime(4n) iii. WHILElintime iv. WHILEptime
2. Consider the following program reverse.
reverse read X {
Y := nil;
while X {
} }
write Y
Y := cons hd X Y;
X := tl X
In which of the following classes is program reverse? (a) WHILEtime(5n)
1
(b) WHILEtime(10n) (c) PWHILE
(d) WHILElintime (e) WHILEptime
3. Let L and M be two timed programming languages with identical data types. Which of the following statements are true? Explain your answer briefly.
(a) L ≼lintime M implies L ≼lintime−pg−ind M
(b) L ≼lintime−pg−ind M implies L ≼lintime M
(c) WH1LE ≼lintime−pg−ind WHILE
(d) WHILE ≼lintime WH1LE
(e) WHILE ≼lintime−pg−ind WH1LE
(f) There are problems that can be decided by a SRAM in cubic
time but not quadratic time.
4. For which thesis do we have sufficient evidence and which?
(a) LIN is robust and does not depend on the sequential notion of computation used.
(b) P is robust and does not depend on the notion of sequential computation used (Cook’s Invariance Thesis).
(c) P is the class of all feasible (= practically decidable) prob- lems (Cook-Karp Thesis).
5. In Lecture 13 we claimed that
L1 ≼lintime L2 implies that LINL1 ⊆ LINL2
Let us prove this now. In other words, assuming that (1) L1 ≼lintime L2 and
(2) A ∈ LINL1
show that also (3) A ∈ LINL2 .
Hint: Unfold the definitions of the assumptions (1) and (2) and to prove goal (3), rearrange the assumptions so that you see that you already have (3). So the “proof” basically requires an under- standing of the definitions and a “re-packaging” of those.
2