# 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 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.

.