# CS代考计算机代写 chain University of Sussex 2 May 2019

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 P􏰇EXP
􏰀 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.
.