University of Sussex Informatics
Spring 2021
Limits of Computation
Feedback for Exercises 7 Dr Bernhard Reus
Time Bounds, Complexity Classes, Hierarchy Theorems
(Lectures 12-15)
1. Consider the following program:
prog read X {
Y:= cons X X
}
write Y
(a) Give a time bound for program for p.
Answer: On the last sheet we already computed that timeWHILE(d) =
2 + (3 + 1) = 6. we observe that the runtime is actually constant and does not depend on the input. A time bound gives for any input size an upper bound of the runtime for all inputs of that size. So any function f : N → N with f(n) = c with c ≥ 6 works as answer.
(b) In which of the following classes is program p?
i. WHILEtime(2n)
Answer: No,asitisnotthecasethat6≤2nforn=1
(recall that our time bounds are worst case).
ii. WHILEtime(4n)
Answer: No,asitisnotthecasethat6≤4nforn=1
(recall that our time bounds are worst case).
iii. WHILElintime
Answer: Yes, as p is in TIME(f) where f(n) = 6n. It is important to observe here that we don’t have any input for which the size is 0. If it were, we would not have that 6 ≤ 6 × 0 = 0.
1
p
iv. WHILEptime
Answer: Yes, as above. Any linear function is also a poly- nomial.
2. Consider the following program reverse.
reverse read X {
Y := nil;
while X {
Y := cons hd X Y;
X := tl X
} }
write Y
In which of the following classes is program reverse?
(a) WHILEtime(5n)
Answer: No, as for d = nil (n = 1) the runtime of the program will be 6 which is not ≤ 5.
(b) WHILEtime(10n)
Answer: Yes. One can check that
timeWHILE (d) = 6 + length(l ) × 10 reverse d
where ld is the list that d encodes. And since in the worst case scenario, we have that length(d) = |d| − 1 one gets:
timeWHILE (d) ≤ 6 + 10(|d| − 1) reverse
So we know that reverse is in WHILEtime(10n−4) and thus reverse must be in WHILEtime(10n).
(c) PWHILE
Answer: No, PWHILE is a problem class!
(d) WHILElintime
Answer: Yes, due to (ii)
(e) WHILEptime
Answer: Yes, due to (ii) and every linear function is in particular a polynomial.
2
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
Answer: No, as the statement on the right is stronger than the one on the left. The slowdown for the simulating M-program is linear but the constant of the linear function must work for all programs.
(b) L ≼lintime−pg−ind M implies L ≼lintime M
Answer: Yes, for the same reasons as given above.
(c) WH1LE ≼lintime−pg−ind WHILE
Answer: Yes, trivially as the original WH1LE-program is also a
WHILE-program. So the program independent constant can be chosen to be 1. (There is no slowdown whatsoever.)
(d) WHILE ≼lintime WH1LE
Answer: Yes, the simulating WH1LE-program needs to store all variables of the original WHILE-program in one variable as a list and must constantly run through this list. However, the length of the list depends on the original WHILE-program and so does the number of occurrences of variables for which one must run through the list. And the number fo variables as well as occur- rences of variables is a constant for each given program. So the slow-down is linear.
(e) WHILE ≼lintime−pg−ind WH1LE Answer: No, the simulating WH1LE- program needs to store all variables of the original WHILE-program in one variable as a list and must constantly run through this list. How much time this takes depends on how many variables the original WHILE-program has and this is therefore not program independent.
(f) There are problems that can be decided by a SRAM in cubic time but not quadratic time.
Answer: This follows from the Asymptotic Hierarchy Theorem if we interpret cubic time as O(n3) and quadratic time as O(n2). The assumptions of the Theorem are all given then as n2 ∈ o(n3) and n2 and n3 are clearly both time constructible.
4. For which thesis do we have sufficient evidence and which?
3
(a) LIN is robust and does not depend on the sequential notion of computation used.
Answer: It is not very robust as compiling e.g. from WHILE to TM produces a polynomial slow-down leading out of LIN. So ths is clear evidence against the above thesis.
(b) P is robust and does not depend on the sequential notion of computation used (Cook’s Invariance Thesis).
Answer: Yes, we have evidence for this thesis, as we can compile between all sequential notions of computation and the slow-down is always at most polynomial, thus not leading out of P.
(c) P is the class of all feasible (= practically decidable) problems (Cook-Karp Thesis).
Answer: There is weak evidence for this thesis, as there are spe- cific examples that contradict it. Problems that can be solved only in polynomial time where the polynomial has a large degree are not really feasible, although in practice natural problems that are known to be in P usually have polynomial bounds of low de- gree (up to 3 or 4, but this can already be problematic for large inputs). On the other hand there are algorithms with exponen- tial worst case complexity that run reasonably well on data used in practice. Thus one can say that P is a good rule-of-thumb description of feasible problems, but it surely does not describe exactly the feasible ones.
5. In Lecture 13, Slide 14 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 the proof goal (3), then rearrange the assumptions so that you see that you already have (3).
Answer:
LINL is the class of all problems of words/strings containing of 0 and 1 that are decidable by a L program that has a running time bounded by a linear function. Formally,
LINL = {A ⊆ {0, 1}∗ | A is decided by a program in Llintime} 4
L1 ≼lintime L2 means that language L2 can simulate language L1 up to linear time difference .
This means that for any L1 program p there is a L2 program q with exactly the same behaviour but for runtime of q we can guarantee only a time bound that is up to a constant (program dependent) factor the time bound of the original program p. The latter, in turn, means for all input data d we have
timeL2 (d) ≤ a ×timeL1 (d)) qpp
Let us show that L1 ≼lintime L2 implies that LINL1 ⊆ LINL2 .
So we assume that L1 ≼lintime L2. (Assumption 1) We have to show that for an arbitrary problem (set) A ∈ LINL1 (Assumption 2) that it is also in LINL2 , i.e. A ∈ LINL2 (3).
The latter means we need to show that there is a L2 program q that decides A in linear time. How do we get this program? Well by Assumption 2 we have a L1 program p that decides A in linear time. From Assumption 1 we know that we can simulate L1 programs by L2 programs, which increases the runtime by at most a constant (linear) factor. In other words, the given program p can be compiled into a L2 program q with the same behaviour, which means q also decides A. We’re halfway there as we have found our decision procedure q. We still have to show that its runtime is linearly bounded. But we know by Assumption 1 that:
timeL2(d)≤a ×timeL1(d)) qpp
and by Assumption 2 that
timeL1 (d) ≤ c × |d|
for some constant c. So from the latter inequality we can infer that a ×timeL1(d))≤a ×(c×|d|)
ppp
p
Now from the last and the first inequality, by transitivity of the order- ing ≤, we get that
timeL2(d)≤a ×(c×|d|) qp
which by associativity of multiplication can be written as : 5
timeL2(d)≤(a ×c)×|d| qp
which completes the proof.
6