CSC 363 — Assignment 3
Due Monday, March 25th, 5:00pm
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources
(people, print, electronic) outside the course and lecture notes, that you consulted.
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct but that are hard to understand may not receive full marks. Mark values for each question are contained in the [square brackets].
I will be in my office all Monday afternoon (on the 25th) or you can put the assignment in my mailbox in DH 3008.
1. Consider a Turing machine which takes as input an encoding of a list of m positive binary numbers. For example, the input may look like 101#100#000, to encode the list [5, 4, 0]. Assume that this sort of encoding is used for all valid inputs. Let n be the total length of the encoding (the length of the input), and let k denote the numeric value of the largest number in the list (for the previous example k = 5). Let this Turing machine be an f(n)−Turing machine. Does f(n) = O(g(n)), where g(n) is some polynomial if:
SOL: The key here is to realize as k grows linearly, n grow logarithmically (or as n grow linearly, k grow exponentially), and as m grows linearly, n grows linearly. So k = Θ(2n) and m = Θ(n).
(a) f(n) = n2 logm
SOL: Yes, f (n) = O(n2 log n). When the runtime is polynomial strictly the size of the input, it’s called strongly polynomial.
(b) f(n) = m2k
SOL: No, f(n) = Ω(n22n). When the runtime is polynomial in the numerical value of the input, it’s called pseudo polynomial.
(c) f(n)=m(logn)(logk)
SOL: Yes, f (n) = O(n2 log n). When the runtime is logarithmic in the numerical value of the input, it’s called weakly polynomial.
For each answer, give a brief justification (one or two sentences). [7]
2. Answer T/F for each question below, as well as give a brief justification for you answer
(one or two sentences). [8]
(a) For all problems B, Sorted ≤P B, where Sorted is the problem of determining if a list of integers is sorted.
SOL: If you said false because nothing can be reduced to {} or Σ∗, OR if you said true because you could just ignore the B black-box and solve Sorted directly you
1
will get full marks.
(b) IfAcanbesolvedinO(2n)andA≤P BthenB∈/P.
SOL: False, just because A is O(2n) does not imply that A is not (for instance) O(1). Therefore, it could still be the case that A reduces to some problem in P.
(c) If there is no known polynomial time algorithm to solve A and A ≤P B then there is no known polynomial time algorithm to solve B.
SOL: True. If B could be solved in polynomial time, then A could be reduced to it and then also solved in polynomial time.
(d) If B can be solved in constant time, and A ≤P B, then A can be solved in constant time.
SOL: False. Consider A to be the problem of determining if a list is sorted, and let B be the problem of determining if the input is 0.
3. Consider the Set-Construction problem: given sets C and S, where S is a set of subsets of C, find a smallest subset of S, denoted by T, such that the union of all the elements of T equals C. For example, let
C = {1,2,3,4,5,6,7}
S = {{1,2,3},{2,4},{6,7},{5,7},{3,4,5},{5,6},{1}}.
Then, T = {{1, 2, 3}, {3, 4, 5}, {6, 7}}, since
{1, 2, 3} ∪ {3, 4, 5} ∪ {6, 7} = C
and there does not exist a two element subset of S such that said subset is a set construc- tion of C. Let
Set-Construction = {< C, S, k > |Over C and S there exists a set construction of size k or less}. Show that: Vertex Cover ≤P Set-Construction. [10]
SOL: To prove Vertex Cover ≤P Set Construction it must be shown that given a gen- eral instance of the Vertex Cover problem, one can use a black box solution to the Set Construction problem to solve it. Note, in the Set Construction problem you’re trying to totally “cover” C, whereas in the Vertex Cover problem you’re trying to cover the set of edges E.
Given a Vertex Cover problem (G, k) where G = (V, E), create a Set Construction problem as follows.
(a) LetC=E
2
(b) Let S = ∅ (for now)
(c) For each vertex v ∈ V find the set of edges which are incident to it, let this set be {(v, w1), (v, w2), …, (v, wm)}, where m is the number of edges incident to v. Add that set of edges to the set S.
(d) Then ask the black box solution if there’s a Set Construction (C,S,k), if there is, then there’s a Vertex Cover (G, k)
Note that each corresponding vertex will create a set of edges it “covers” and then there’s a Set Construction of size k iff there’s Vertex Cover of size k.
3