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