Explain, with the aid of an example, how conditional instructions may be used to reduce the number of bubbles in a pipeline. [4 marks] (c) What is the difference between branches, interrupts, software interrupts (initiated by a SWI instruction on the ARM) and exceptions? [8 marks] (d) Evil Robot's internal systems have been constructed using the situation calculus and a theorem prover. (a) Describe the situation calculus, concentrating on the fundamental elements that you would expect to see independently of any specific problem. [5 marks] {P(x, x)} {P(x, f(x))} {P(x, y), P(y, z), P(x, z)}

[6 marks]

(c) Derive the empty clause using resolution with the following set of clauses, or

give convincing reasons why it cannot be derived. (Note that a and b are

constants.)

{P(a)} {Q(a)} {R(b)} {S(b)}

{Q(x), P(x), R(y), Q(y)} {S(x), R(x), Q(x)}

[7 marks]

10 Complexity Theory

(a) Explain what it means to say that a problem is

(i) NP [2 marks]

(ii) NP-Complete [2 marks]

(b) Define the standard problem 3-SAT and describe how you would take an

instance of it and derive an integer n that you would use in any formulae

relating to the cost of solving that instance. [3 marks] Describe a protocol for a node to learn about its immediate neighbours. You should specify the format of your messages and the size of any message fields. [4 marks] (ii) Using the characteristics of the network described above, design a protocol for distributing this information across the network. You should specify the format of your messages and the size of any message fields

This question relates to binary constraint satisfaction problems (CSPs). A CSP has a set X = {x1, . . . , xn} of variables, each having a domain Di = {v1, . . . , vni } of values. In addition, a CSP has a set C = {C1, . . . , Cm} of constraints, each relating to a subset of X and specifying the allowable combinations of assignments to the variables in that subset. (a) Give a general definition of a solution to a CSP. [1 mark] (b) Given a binary CSP, define what it means for a directed arc xi xj between variables xi and xj to be arc consistent. [2 marks] (c) Give an example of how a directed arc xi xj can fail to be arc consistent. Explain how this can be fixed. [2 marks] What is a non-deterministic Turing Machine? Supposing that some

computation of such a machine takes N steps, what information needs to

be reported to describe exactly how the computation proceeded? In what way

is this relevant to the problem of solving an arbitrary NP problem? [7 marks]

(d) Sketch a proof of Cook's result, that the problem 3-SAT is NP complete.

Justify that any transformations you introduce are polynomial.