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