首页 >
> 详细

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

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28