Alternative assessment: Computability and Complexity Theory, COMP0017 Main Summer Examination period, 2019/20 Answer BOTH of the TWO questions. Marks for each part of each question are indicated in square brackets. Standard calculators are permitted. 1. In the sequel, let code(−) be a computable injective function that encodes Turing ma- chines into strings from {0, 1}∗. a. Give the complete definition (as a tuple) of the following Turing machines. You may define the transition function using diagrams. (For full marks, pay attention to not using more states than needed). (i) A Turing Machine which recognises the language only containing the empty string. (ii) A Turing Machine which decides the empty language. (iii) A Turing Machine which recognises the language of all strings. (iv) A Turing Machine which recognises the complement of Turing machine (a) above. [Question 1 cont. over page] COMP0017 1 TURN OVER [15 marks] b. For each of the following languages, say (without proving it) if it is: (1) decidable; (2) undecidable but recognisable; (3) unrecognisable. Moreover, for each language, say whether Rice’s theorem applies to that language. L1 = {y ∈ {0, 1}? | y = code(M) for some TM M and the language recognised by M is not empty.} L2 = {y ∈ {0, 1}? | y = code(M) for some TM M and M does not halt on code(M)} L3 = {y ∈ {0, 1}? | y = code(M) for some TM M and M halts on input 0.} L4 = {y ∈ {0, 1}? | y = code(M) for some TM M and M halts on strings of odd length.} L5 = {y ∈ {0, 1}? | y = code(M) for some TM M and M halts on at least one string of odd length.} L6 = {y ∈ {0, 1}? | y = code(M) for some TM M and M has five states} [24 marks] c. Consider the language L = {y ∈ {0, 1}? | y = code(M) for some TM M and M halts on code(M)}. Also recall the language HALT , defined as HALT = {〈y, x〉 ∈ {0, 1}? | y = code(M) for some TM M and M halts on input x.} • Prove that HALT mapping-reduces to L, notation HALT ≤ L. • What does this mean for the decidability of L? • Consider the complement L− of L. Based on the fact that HALT ≤ L, what can we infer on the decidability/recognisability of L−? [11 marks] [TOTAL=50 marks] [Question 2 cont. on next page] COMP0017 2 CONTINUED 2. a. Is either of the classes co-NP-hard and EXPTIME-hard contained in the other? If so, explain why. [4 marks] b. An instance (G, k) of the clique problem consists of an undirected graph G and a natural number k. It is a yes instance if G contains a clique C of size k, i.e. a set of k distinct vertices of G such that every pair of distinct vertices from the set forms an edge of G. For each of the following five undirected graphs G find the largest k such that (G, k) is a yes-instance of the clique problem. • • • • • • • • • • • • • • • • • • • • • • • • [5 marks] c. Prove that the clique problem belongs to NP. [3 marks] d. An instance (G, k) of the independent set problem consists of an undirected graph G and a natural number k. It is a yes instance if there is a set S of k distinct vertices of G such that no pair from S is an edge of G. For each of the five graphs G in part (2.b) find the largest k such that (G, k) is a yes-instance of the independent set problem. [3 marks] e. Prove that the independent set problem reduces in p-time to the clique problem. [3 marks] f. Assuming your answers to the previous questions and assuming that the independent set problem is NP-hard (but without further assumptions) what can you conclude (if anything) about the complexity of the clique problem? [3 marks] [Question 2 cont. over page] COMP0017 3 TURN OVER g. Suppose that there is a three-colouring of an undirected graph G, that is, a function f from the vertices of G to {r, y, b} such if (x, y) is an edge of G then f(x) 6= f(y). For which values of k do we know that (G, k) is a yes-instance of the independent set problem? [3 marks] h. The game of tic-tac-toe (or noughts and crosses) is played over a three by three grid (see https://en.wikipedia.org/wiki/Tic-tac-toe for the rules). Give a formal definition of a position (p, P ) in the game, where p tells you where the noughts and crosses currently are, and P ∈ {×, ◦} is the player whose turn it is. Also, define a winning position for either player. [6 marks] i. Define an n× n generalisation of tic-tac-toe, making it clear what the starting posi- tion is, any changes you need to make to the definition of a position, and any changes you have to make to the normal rules, including the rule for a winning position. [6 marks] j. Define a winning strategy for player P , for the n × n game that starts in position (p,Q). [6 marks] k. An instance (n, p, P ) of the generalised tic-tac-toe problem consists of an integer n ≥ 3 and a position p for the n × n game, suitably generalised and a player P ∈ {×, ◦}. It is a yes instance if P has a winning strategy in the game starting from p, it is a no instance otherwise. Give an upper bound on the complexity of this problem (i.e. state whether the problem belongs to P,NP,PSPACE,EXPTIME, . . .? Complete solutions with complete formal proofs are not required here, but justify your answer briefly. [8 marks] [TOTAL=50 marks] COMP0017 4 END OF PAPER
