The subset-sum problem is defined as follows: Given a set S of n positive…

Conclusion: The false statement is: "Q solves the subset-sum problem in polynomial time when the input is encoded in binary"

Explanation:

• Algorithm running time: Q runs in O(nW) time.

• Input encoding matters: For binary encoding, the number of bits needed to represent W is about log W. Expressing the running time O(nW) in terms of the binary input size makes it exponential in that size, so it is not polynomial.

• For unary encoding, W is represented with O(W) symbols, so O(nW) is polynomial in the unary input size. Thus Q is polynomial-time for unary-encoded inputs (this is called a pseudopolynomial algorithm).

• Complexity class facts: Subset-sum is in NP because a candidate subset can be verified quickly, and it is NP-hard, so it is NP-complete. These statements are true.

• Therefore the only false statement is the claim that Q gives a polynomial-time solution under binary encoding; O(nW) is pseudopolynomial but not polynomial in the binary input size.