Let KNAP = {a1#a2# . . . #an#C | ai and C are integers coded in binary, and there is a set I ⊆ {1, . . . , n} such that P i∈I ai = C}. Let UKNAP be the same, except that the integers are coded in unary, i.e., a is represented by 1^{a}, the string comprised of a 1’s. UKNAP is in P but KNAP is NP-complete. Find and explain the flaw in each of the “proofs” below. Make your proofs/counterexamples crisp and explicit.

(a) For any string u in {1, #}^{*} we can easily produce a string v in {0, 1, #}^{*} such that u ∈ UKNAP ⇔ v ∈ KNAP. (E.g., if u = 11#1#11111 then v = 10#1#101.) Furthermore, the transformation can be done in time bounded by a polynomial in the length of u. Thus, P=NP.

(b) For any string v in {0, 1, #}^{*} we can easily produce a string u in {1, #}^{*} such that v ∈ KNAP ⇔ u ∈ UKNAP. Furthermore, the transformation can be done in time bounded by a polynomial in the length of u. Thus, P=NP

(c) 1-of-3-SAT is another known NP-complete variant of the satisfiability problem: it is the set of Boolean formulas in conjunctive normal form with exactly 3 literals per clause such that the formula is satisfied by a truth assignment making exactly one literal in each clause true. Let f be a formula in conjunctive normal form with exactly 3 literals per clause (3CNF). Suppose it has clauses c1, . . . , cq and variables x1, . . . , xm, m ≤ 3q. Suppose “xi” occurs in clauses numbered i1, . . . , ij

and “BAR xi” occurs in clauses numbered i’1…i’j. Let ai = SUM from k=1 to j of ik, and BAR ai = SUM from k = 1 to j’ of i’k . Let s = SUM from i = 1 to q of i.

Generate the string: u = 1^{a1}#1^{BAR} ^{a1}# . . . #1^{am}#1^{BAR am}#1^{s}

Now if f is satisfiable by an assignment that makes exactly one literal per clause true, i.e. if f is in 1-of-3-SAT, then u is in UKNAP: Pick ai or BAR ai depending on whether xi is true or false respectively in the 1-of-3 satisfying assignment. Every clause is satisfied by exactly one literal, so the sum of the chosen a, BAR a’s is

exactly s. Thus u ∈ UKNAP. Further the reduction can be done in time polynomial in the length of f; e.g., note that the numbers ai, BAR ai, and s are all of magnitude at most q, since each is the sum of at most q distinct numbers between 1 and q, so the length of u is O(q^3)) = O(|f|^3)).

Thus P=NP.