Subset Sum has a dynamic programming solution that runs in O(n·S) time, where n is the number of items and S is the target sum. A student claims this proves Subset Sum is in P. What is wrong with this reasoning?
ANothing is wrong — O(n·S) is polynomial in the input size, so it proves Subset Sum is in P
BO(n·S) is polynomial in the numeric value of S but exponential in the number of bits needed to encode S, making it pseudo-polynomial rather than truly polynomial
CThe student is wrong because dynamic programming cannot solve NP-complete problems at all
DThe student is wrong because the correct complexity is O(n²·S), which is clearly not polynomial
The subtle point is what 'polynomial' means relative to input size. The input to Subset Sum is not the number S itself but the binary encoding of S, which has log₂(S) bits. So the runtime O(n·S) is actually O(n·2^(log S)) — exponential in the bit-length of S. A truly polynomial algorithm would run in time polynomial in n and log S. When S is small relative to n, the DP is fast in practice. When S is exponentially large (say, S ≈ 2^n), the DP is just as slow as brute force. This is precisely the pseudo-polynomial vs. polynomial distinction.
Question 2 Multiple Choice
Under which condition would Subset Sum instances be efficiently solvable in practice, despite being NP-complete in the worst case?
AWhen the integers are all small — bounded by a polynomial function of n — so the target sum S is also polynomially bounded
BWhen the target is exactly half the total sum (the Partition variant), which is always easier than general Subset Sum
CWhen the integers are all powers of 2, because binary representations are always easy to sum
DWhen the items are sorted in decreasing order, enabling greedy pruning
The O(n·S) DP is efficient when S is small relative to n. If each integer is at most some polynomial p(n), then S ≤ n·p(n), which is also polynomial in n, and the DP runs in polynomial time. This is exactly what 'weakly NP-complete' means: the hardness is tied to the magnitude of the numbers, not their count. Real-world instances often have this property (e.g., prices measured in cents rarely exceed millions), which is why the DP approach is practical despite the worst-case intractability.
Question 3 True / False
Partition is a special case of Subset Sum where the target is exactly half the total sum of all elements.
TTrue
FFalse
Answer: True
Partition asks: can we split a set into two subsets with equal total? If the full set has total T, we need each half to sum to T/2. This is exactly Subset Sum with target T/2. Because Partition reduces to Subset Sum, and Subset Sum reduces to Partition (Partition can encode any Subset Sum instance with padding), the two problems are equivalent in complexity. Both are NP-complete, both admit O(n·S) pseudo-polynomial DP, and both are weakly NP-complete.
Question 4 True / False
Since Partition and the 0-1 Knapsack problem are both NP-complete, they have the same approximability — any approximation scheme that works for one should work for the other.
TTrue
FFalse
Answer: False
NP-completeness is a coarse classification that says nothing about approximability. Knapsack (with values and a capacity) admits a fully polynomial-time approximation scheme (FPTAS): you can get within any (1−ε) factor of optimal in polynomial time. Partition has no polynomial-time approximation scheme (PTAS) unless P = NP — even getting close to the optimal split is hard. Two NP-complete problems with nearly identical descriptions can inhabit completely different parts of the approximation hierarchy. This is one of the deepest lessons from the study of these problems.
Question 5 Short Answer
What does it mean for a problem to be 'weakly NP-complete' rather than 'strongly NP-complete,' and why does this distinction matter practically?
Think about your answer, then reveal below.
Model answer: A problem is weakly NP-complete if it is NP-complete in general but solvable in polynomial time when the numeric values in the input are bounded by a polynomial in the input length (i.e., it admits a pseudo-polynomial algorithm). Partition and Subset Sum are weakly NP-complete because their O(n·S) DP runs efficiently when numbers are small. A strongly NP-complete problem, like 3-SAT or graph coloring, remains NP-hard even when all numeric values are bounded by a polynomial — there is no pseudo-polynomial escape hatch. The distinction matters practically because weakly NP-complete problems are often tractable on real inputs where numbers happen to be small, while strongly NP-complete problems offer no such relief.
The weak/strong distinction is invisible from the NP-completeness certificate alone — it requires examining whether the hardness comes from large numbers or from combinatorial structure. Understanding this guides the choice of algorithm: pseudo-polynomial DP for weakly NP-complete problems, approximation algorithms or heuristics for strongly NP-complete ones.