Answered! 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…

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.