Complexity Theory Supervision Work

Table of Contents

Supervision 1

Question 1.1

Explain what it means to say that a problem is

  1. NP [2 marks]
  2. NP-complete [2 marks]

Question 1.2

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. (I.e. how do you measure the input size.) [3 marks]

Question 1.3

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]

Question 1.4

Sketch a proof of Cook’s result, that the problem 3-SAT is NP-complete. Justify that any transformations you introduce are polynomial. [6 marks]

Question 1.5

Give a precise definition of what it means for one decision problem to be polynomial-time reducible to another. [3 marks]

Question 1.6

Let Subset Sum denote the following decision problem: Given a set of positive integers \(S = {v_1, \ldots, v_n}\) and a number \(t\), determine whether there is a subset of \(S\) that sums to exactly \(t\).

  1. Explain why Subset Sum is in NP. [3 marks]
  2. Describe a polynomial-time reduction from the problem of 3-dimensional matching to Subset Sum. [9 marks]
  3. Explain why this implies that Subset Sum is NP-complete. [3 marks]

Question 1.7

Consider the following two decision problems:

  • HamCycle: Given a graph \(G = (V, E)\) does it contain a cycle that visits every vertex exactly once?
  • HamPath: Given a graph \(G = (V, E)\) and two distinguished vertices \(s, t \in V, s\neq t\), is there a simple path in \(G\) that starts at \(s\), ends at \(t\) and visits every other vertex exactly once?

Show that HamCycle is polynomial-time reducible to HamPath. [8 marks]

Question 1.8

The following decision problem is known to be solvable in polynomial time: EulerCycle: Given a graph G = (V, E) does it contain a cycle that visits every edge exactly once? What can you conclude about the truth of the following statements? Justify your answers.

  1. EulerCycle is polynomial-time reducible to HamCycle. [3 marks]
  2. EulerCycle is polynomial-time reducible to HamPath. [3 marks]
  3. HamPath is polynomial-time reducible to EulerCycle. [3 marks]

Supervision 2

Question 2.1

Suppose that you were provided with a black box that could accept the language of sentences describing an integer k and a graph \(G\) with a $k$-clique, and the black box accepted such languages in polynomial time. Explain how you could derive a process that would accept satisfiable instances of the problem 3-SAT in polynomial time. [10 marks]

Suppose instead you had been provided with a black box that provided a polynomial-time acceptor for 3-SAT. Explain how you could use that to derive an efficient acceptor for the clique problem. [10 marks]

In your explanation the level of detail you are expected to give should be tuned to the level of complication in any transformations that you need to describe: simple ones should be described and justified in detail while elaborate or messy ones can be sketched and standard results quoted.

Question 2.2

When defining space-complexity we use two-tape Turing Machines, with a read-only tape for input data and a read–write working tape. We count only the space used on the work tape. What difference would be made if we worked with standard one-tape Turing machines, loaded the input data onto the tape to start with and measured space in terms of total tape cells touched by the end of the computation? [4 marks]

Question 2.3

Comment on the following:

The problem of finding a factor of a number \(n\) is NP, because if we have a factor \(k\) of \(n\) we can do a simple trial division and check it in time related to \(\log(n)\). Thus finding factors of numbers of the form \(2^p - 1\) (these are known as Mersenne Numbers) is a problem in the class NP.

[2 marks]

Question 2.4

Define the class co-NP. State an example of a problem that lies in it. [2 marks]

Question 2.5

What is a witness function for an NP problem? Why might some problem such as 3-SAT have many different witness functions associated with it? [2 marks]

Question 2.6

Give and justify a relation between \(NTIME(f(n))\) and \(SPACE(f(n))\). [4 marks]

Question 2.7

Matchings on bi-partite graphs can be found in polynomial time. The matching problem on tri-partite graphs is known to be NP-complete. Does this suggest that the corresponding problem with a graph whose nodes are partitioned into four sets (“quad-partite” matching) is liable to be exponential in complexity? Justify your answer. [4 marks]

Question 2.8

Comment on the following proposition:

Determining which player can force a win from a given starting position in the game of Chess is an NP problem because given any sequence of moves it will be easy to verify that they are all legal moves and easy to see who wins at the end of them.

[2 marks]

Question 2.9

Let Bounded Factor denote the following decision problem:

Given positive integers \(n\) and \(k\), decide whether \(n\) has a proper factor that is less than \(k\).

For each of the following questions, give a detailed justification of your answer. Note that, in some cases, the answer may not be a simple “yes” or “no” but may instead be linked to open problems in complexity theory such as whether P = NP or the existence of one-way functions. In such cases, you should clearly explain the links and state what the consequences might be of both a positive and a negative answer to the question.

  1. Is Bounded Factor in NP? [4 marks]
  2. Is Bounded Factor in co-NP? [4 marks]
  3. Is Bounded Factor NP-hard? [6 marks]
  4. Is Bounded Factor in P? [6 marks]

Supervision 3

Question 3.1

Define a one-way function. [4 marks]

Question 3.2

Explain why the existence of one-way functions would imply that P \(\neq\) NP. [7 marks]

TODO Question 3.3

Recall that Reach is the problem of deciding, given a graph G a source vertex s and a target vertex t, whether G contains a path from s to t; and Sat is the problem of deciding whether a given Boolean formula is satisfiable. For each of the following statements, state whether it is true or false and justify your answer.

  • If Reach is NP-complete then P = NP. [3 marks]
  • If Reach is NP-complete then NP ≠ PSPACE. [3 marks]
  • If Sat is PSPACE-complete then NP = PSPACE. [3 marks]

TODO Question 3.4

Give definitions for the complexity classes SPACE\((f)\) (for any function \(f\)); L and NL. [6 marks]

TODO Question 3.5

Consider the following decision problem:

Reachability: Given a graph \(G = (V, E)\) and two distinguished vertices \(s, t \in V\), does \(G\) contain a path from \(s\) to \(t\)?

  • Explain why Reachability is in the complexity class NL. [7 marks]
  • Show that if Reachability were in the class L, we would have L = NL. [7 marks]

Author: Robert Kovacsics (rmk35)

Created: 2019-04-01 Mon 15:19

Validate