University of Sussex 2 May 2019
Limits of Computation Test
⇒→→→→→→→→→→ → → 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 { [0,
if tl A {
while hd B
{ B:= tl A } }
else{ } }
write B
⟨ ⟨ nil.nil ⟩.⟨ nil.nil ⟩ ⟩ ⟨ [0].[0,1] ⟩ ⟨ [0,1].⟨ nil.nil ⟩ ⟩
⟨1.⟨0.[1]⟩⟩ ⟨1.[nil,1]⟩ ⟨⟨nil.nil⟩.⟨nil.⟨nil.nil⟩⟩⟩
3. Which of the following problems are undecidable? Tick the ones that are.
Halting Graph Colouring Postman Primality Tiling TSP
4. Complete the sentence: “For an L-program p, the term [p]L denotes the semantics of which is a function of type → .”
5. The class of problems decidable by a WHILE-program is the same as the class of programs decidable by a TM-program. Is this correct? Tick: yes no.
Give a short reason: .
6. Complete the sentence: “A L-semidecidable problem is L-decidable if, and only if, .”
7. Complete the sentence: “To show that the Halting Problem, HALT, is WHILE- semidecidable we proved that
is a semidecision procedure for it.”
8. Complete the definition of the operational semantics of WHILE assignment :
X := E ⊢ σ→σ[ := ] if E = v.
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 2 3 ”. P.T.O
]
2. Tick those terms below that are encoded by the same binary tree as list [1, 0, 1] .
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
11. Complete the Cook-Karp (Cobham Edmonds) thesis: “The
problems are exactly those in .”
12. Assume we have a WHILE-program p such that timeWHILE(d) = 2|d|2 + 300.
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
p ∈ WHILElintime p ∈ WHILEptime
timeWHILE is in o(n2) p
13. Define the class NPTM (either of the two definitions is fine): “A problem A is in NPTM iff
. TSPisinPTAS TSPisinAPX 0-1KnapsackisinPTAS
14. Tick only the correct statements:
P⊆RP PTAS⊆APX MetricTSPisinAPX
15. Complete: “SAT is defined as follows: F ∈ SAT iff F is a Boolean formula in normal form and .
16. True, false or unknown? Tick the correct box for each case.
TIMEWH1 LE (6n) TIMEWH1 LE (7n) TIMETM(O(4n)) TIMETM(O(n2)) PTM ⊆ NPTM
Graph Colouring is in P
0-1 Knapsack is NP-complete PEXP
unknown true false unknown true false unknown true false unknown true false unknown true false unknown true false
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.
.