University of Sussex 2 May 2019
Feedback Limits of Computation Test – Dr Bernhard Reus
⇒→→→→→→→→→→ → → CandidateNo.
• Please answer ALL questions by writing on THIS SHEET. You are not
allowed to use any other documents or devices.
• Please write your candidate number in the box above.
• Questions are equally weighted (but Q1 – Q2 which have 2 extra marks each). Special “Spring” treat: your lowest scoring answer won’t count.
• You have 40 minutes to answer all 17 questions.
1. On the right hand side, write the program-as-data representation of the WHILE- program on the left (variable numbers start at 0):
test read A {
if tl A {
while hd B
{ B:= tl A }
[0,
[ [if,[tl,[var,0]],
[ [while,[hd,[var,1]],
[ [:=,1,[tl,[var,0]]]] ]
} ], else{ } []
}]
write B ],1]
Typical mistakes Forgetting the list brackets for the blocks (program, then and else branch, while body). Forgetting the var to encode variables as expressions, forgetting the output variable 1 at the end.
2. Tick those terms below that are encoded by the same binary tree as list [1, 0, 1] .
⟨ ⟨ nil.nil ⟩.⟨ nil.nil ⟩ ⟩ √ ⟨ [0].[0,1] ⟩ ⟨ [0,1].⟨ nil.nil ⟩ ⟩
√ ⟨1.⟨0.[1]⟩⟩ √ ⟨1.[nil,1]⟩ ⟨⟨nil.nil⟩.⟨nil.⟨nil.nil⟩⟩⟩
Typical mistakes Not ticking ⟨ [0].[0,1] ⟩, i.e. not recognising [0] is encoded by the same tree as 1.
3. Which of the following problems are undecidable? Tick the ones that are.
√ Halting Graph Colouring Postman Primality √ Tiling TSP
Typical mistakes Forgetting to tick Tiling; wrongly ticking TSP or Postman which are decidable, of course.
4. Complete the sentence: “For an L-program p, the term [p]L denotes the semantics of program p which is a function of type L-data → L-data⊥ .”
Typical mistakes Forgetting the ⊥ at the end, as the semantics is a partial function (as the program may not provide a result due to divergence). Instead of L-data all kinds of random letters appeared often.
5. The class of problems decidable by a WHILE-program is the same as the class of pro-
grams decidable by a TM-program. Is this correct? Tick √ yes no.
Give a short reason: The Church-Turing Thesis (or: “RAM ≡ TM, i.e. RAM≼ TM and TM≼ RAM”) .
Typical mistakes This has been done well by most.
6. Complete the sentence: “A L-semidecidable problem is L-decidable if, and only if, its complement is semidecidable too
(Alternative correct answer: it can be reduced to a decidable problem).”
Typical mistakes This has been done well by most if one accepts the alternative answer, which I did. Some students wrote random things however.
7. Complete the sentence: “To show that the Halting Problem, HALT, is WHILE- semidecidable we proved that the universal program for WHILE
(or the self-interpreter for WHILE) is a (L-)semidecision procedure for it.”
Typical mistakes No typical mistakes come to mind here. Some students wrote of
all kinds of decision procedures and halting and things like that.
8. Complete the definition of the operational semantics of WHILE assignment :
X:=E⊢σ→σ[X:=v] if EE σ =v.
Typical mistakes Writing σ[ X := E] instead of σ[ X := v]. Using σ′ where there
is no such thing around in this case.
9. Rice’s Theorem says that certain kind of problems are undecidable. Complete: “To satisfy the conditions of Rice’s Theorem a problem must be . . .
1 about programs 2 non-trivial 3 extensional ”.
Typical mistakes “about programs” has not been answered by too many. Often “undecidable” or “hard” was used. Some students wrote “extensionable” or similar stuff instead of “extensional”. This was marked as half correct or correct, depending on how similar it sounded wrt. the right answer.
10. Which of the following problems x ∈ A? can be shown to be undecidable by applying Rice’s Theorem? Tick the right box in each case:
(a) A = { p ∈ D | p is a WHILE-program-as-data that tests whether its argument is 6 } decidable √ undecidable by Rice’s theorem
(b) A = { p ∈ D | p is a WHILE-program-as-data such that timeWHILE(nil) > 456 }
p
√
decidable undecidable by Rice’s theorem
(c) A = { p ∈ D | p is a WHILE-program-as-data that returns nil for any input }
decidable √ undecidable by Rice’s theorem
Typical mistakes No typical mistakes. Answers were (like every year) all over the place. Many students guessed (I think one can safely assume they guessed) all wrongly.
11. Complete the Cook-Karp (Cobham Edmonds) thesis: “The tractable (or feasible) problems are exactly those in P.”
Typical mistakes Writing something from the Church-Turing or more often, Cook’s Invariance thesis. Marked very generously.
12. Assume we have a WHILE-program p such that timeWHILE(d) = 2|d|2 + 300. p
Tick only the statements that are correct.
p ∈ WHILEtime(f ) where f (n) = 9n2 + 291 √ p has a runtime bound in O(n2 log n)
p ∈ WHILEtime(f) where f(n) = n2 + 300n
p ∈ WHILElintime √ p ∈ WHILEptime
timeWHILE is in o(n2) p
Typical mistakes O(n2 log n) has been ticked by most correctly, but often the first
and third box on the left were ticked as well. Both should not be ticked because the
function f is not a time bound for all inout. If the size of the inout is 1 it is not,
for instance. Moreover, timeWHILE is in o(n2) has been ticked often but this is wrong. p
It’s actually wrong on two levels. timeWHILE is of the wrong type, it’s not a runtime p
bound itself. Moreover, little o is about growing much more slowly and this is not the case here wither as both polynomials have the same degree.
13. Define the class NPTM (either of the two definitions is fine): “A problem A is in NPTM iff A has an TM-verifier that runs in polynomial time
or: A is accepted by a nondeterministic Turing machine with polynomial runtime .
Typical mistakes Many students guess things randomly here or explained P rather than NP. Some also gave results about NP rather than a definition. This was marked generously then.
14. Tick only the correct statements:
TSPisinPTAS TSPisinAPX √ P⊆RP √ PTAS⊆APX
√
0-1KnapsackisinPTAS √ MetricTSPisinAPX
Typical mistakes Here all kinds of mistakes were made (probably by guessing).
15. Complete the sentence: “The SAT problem is a problem about boolean formulae. A boolean formula F is in SAT iff F is in conjunctive normal form and
F is satisfiable .
Typical mistakes Here all kinds of random things appeared (probably by guessing). Many students opted for database normal forms :-). Many students wrote things about F that did not honour the fact that F is a bopolean formula, e.g. talking about it as if it were a problem.
16. True, false or unknown? Tick the correct box for each case.
TIMEWH1LE(6n) TIMEWH1LE(7n) TIMETM(O(4n)) TIMETM(O(n2)) PTM ⊆ NPTM
Graph Colouring is in P
0-1 Knapsack is NP-complete P EXP
unknown √ true false unknown √ true false unknown √ true false √ unknown true false unknown √ true false unknown √ true false
Typical mistakes Here all kinds of mistakes were made (probably by guessing). Graph Colouring is in P was often wrongly ticked as false. We don’t know this for sure. Note that the first two boxes were the two kinds of Hierarchy Theorems.
17. The CANDYCRUSH Problem is defined as follows.
Instance: an n×m board filled with coloured candies (6 possible colours), a number k and a score s to be achieved or beaten. The score for a sequence of swaps equals the number of chains of 3 identical candies deleted.
Question: Is there a sequence of k swaps which obtains a score of s or more?
Tick all correct answers: CANDYCRUSH is known to be
√ decidable inLIN inP √ inNP
Give an example of a statement that if proven would imply that CANDYCRUSH is NP-hard. The statement must not involve the definition of NP-hard.
SAT (or any NP-complete problem) ≤p CANDYCRUSH Alternative (unintended) answer that can’t be faltered: NP=P).
Typical mistakes A number of students ticked wrong boxes, often P. Some stu- dents gave NP=Pas an answer which was accepted, although this provides a sort of pathological situation where NP and NP-complete coincide. Some students gave the reduction answer but swapped the roles of SAT (or any other NP-complete problem) and CANDYCRUSH.