CSC 363 Winter 2007 — Assignment 3

Due: 2pm on March 23rd. See course webpage for up-to-date information on due date.
Worth: 10% of your course grade.

1. [20 marks]

   Let N be a decider nondeterministic TM. That is, on any input, all computation paths are finite. In class and in the textbook, the following definitions are used:

   • T_N(w) is the length of the longest path in the computation tree of N on input w.
   • T_N(n) is the maximum of T_N(w) for all w of length n.
   • NP consists of languages L such that there exist a NTM N and an integer k such that L=L(N) and T_N(n)=O(n^k).
   In this problem, we consider an alternative definition of the running time of a nondeterministic TM.
   • T′_N(w) is the length of the shortest path in the computation tree of N on input w leading to an accepting configuration. Define T′_N(w)=0 if no accepting configuration exists, i.e. if N does not accept w.
   • T′_N(n) is the maximum of T′_N(w) for all w of length n.
   • NP′ consists of languages L such that there exist a NTM N and an integer k such that L=L(N) and T′_N(n)=O(n^k).
   So, looking at the computation tree of N on input w, instead of measuring the length of the longest path to any configuration, accepting or rejecting, we measure the shortest path to an accepting configuration.

   Show that the two definitions are equivalent: NP = NP′. In other words, show that for any language L, there exist N and k such that L=L(N) and T_N(n)=O(n^k) iff there exist N′ and k′ such that L=L(N′) and T′_N′(n)=O(n^k′).

2. [20 marks]

   Consider the following problem: given n and t, can we write n as the product of t prime numbers? Remember, 1 is not a prime number. We formalize this problem as a language membership problem as follows.

   NUMPRIMEDIVS = { <n,t> : n = p₁*...*p_t where for all i, p_i is a prime number }

   Show that NUMPRIMEDIVS is in NP.

3. [30 marks]

   For each language below, show that it belongs to one of P, NP, or coNP. Give the strongest answer you can, together with a brief justification.

   1. LONGPATH = { <G,s,t,k> : G is an undirected graph that contains a simple path of length at least k between s and t }.
   2. SHORTPATH = { <G,s,t,k> : G is an undirected graph that contains a simple path of length at most k between s and t }.
   3. DENSESET = { <G,k> : G is an undirected graph such that every set of at least k vertices contains at least one edge of G }.

   Note: a path is simple if it contains no repeated vertices. In your proofs, you may use without proof the following fact: there are polynomial time algorithms that, given a graph and two vertices, output the length of the shortest path between these two vertices. Dijkstra's algorithm is such an example.

4. [20 marks]

   A formula in CNF is monotone if it does not contain any negated variable. For example,

   (x₁∨x₂∨x₃) ∧(x₁∨x₄) ∧(x₂∨x₄)

   Monotone formulas are always satisfiable (by setting all variables to true) but we can ask if it is possible to satisfy a monotone formula by setting fewer variables to true (e.g. the formula above can be satisfied by setting x₁ and x₄ to true, but not by setting only one variable to true).

   Consider the following problem: given a monotone CNF φ and some k, is there a satisfying assignment for φ that sets at most k variables to true? We formalize this problem as a language membership problem as follows.

   MONOTONESAT = { <φ,k> : φ is a monotone CNF formula that can be satisfied by setting at most k variables to true }

   Show that MONOTONESAT is NP-complete.