skip to content

Knapsack is stated as maximise the value loaded, yet NP-completeness is defined for yes-or-no problems, so how is Knapsack made one?

level: middleimportance: should knowfreq 46%

answer

  1. classes are defined over yes-or-no questions
  2. add a target value K
  3. certificate is the chosen subset
  4. binary search recovers the optimum
  5. optimisation is NP-hard, not NP-complete

basics

~20 s

Add a threshold. The decision form asks whether some selection fits the capacity and reaches at least value K. That yes-or-no form is NP-complete, and a threshold oracle recovers the optimum by binary search over K.

solid answer

~40 s

NP-completeness is defined for decision problems, so the optimisation statement is turned into one by adding a target: `is there a selection of parcels of total weight at most C whose total value is at least K?` A yes answer has a short certificate - the selection itself, checked by two additions and two comparisons - which is what membership in NP needs. The two versions are polynomially equivalent: an optimiser answers any threshold question in one call, and a threshold oracle finds the optimum by binary search over K, using about as many calls as the total value has bits. So the decision version is NP-complete while the optimisation version is NP-hard - hard, but not itself a member of NP, because it returns a number rather than a yes or a no.

go deeper

for a junior

Recall that the hardness catalogue is written about yes-or-no questions, and that a maximise-style requirement is turned into one by adding a target number to beat.

for a middle

Explain both conversions: an optimiser answers a threshold in one call, and a threshold routine finds the optimum by binary search over the target, at a logarithmic number of calls.

for a senior

Demonstrate the precision that matters in review: the threshold version is NP-complete, the maximise version is NP-hard, and a component that only answers feasibility is already enough to build the optimiser.

for a principal

Frame it for a roadmap: because the versions are polynomially equivalent, no restatement of the requirement escapes the hardness, so the decision to make is about which instances you accept, not about how the ask is phrased.

## Why a threshold is needed at all The classes **NP** and **NP-complete** are defined over **decision problems**: questions whose answer is yes or no. The definition leans on that shape. A problem is in NP when every yes-instance has a short **certificate** that a polynomial-time checker accepts, and there is no obvious meaning for a certificate of the answer `the best load is worth 4,180`. A depot's real requirement - load the van with the most valuable parcels it can carry - is an optimisation problem. To classify it you restate it with a target value `K`: > Given parcel weights, parcel values, a capacity `C` and a target `K`, is there a subset of parcels whose total weight is at most `C` and whose total value is at least `K`? That is the decision version of Knapsack, and it is the one the catalogue lists as NP-complete. ## What the threshold buys The restatement is not bookkeeping; it makes both halves of an NP-completeness claim expressible: - **Membership.** A yes-instance's certificate is the chosen subset. Checking it is two sums and two comparisons - linear in the instance - so the decision version is in NP. - **Hardness.** The decision version can be shown at least as hard as a known complete problem, which is only a meaningful statement between problems of the same yes-or-no shape. Notice what the certificate does **not** do. It proves a yes; it says nothing about a no. Certifying that *no* selection reaches `K` would mean ruling out every subset, and no short certificate for that is known - which is the same asymmetry that separates NP from co-NP. ## Moving between the two versions The threshold form is not a weaker question in disguise. The two versions convert into each other in polynomial time: 1. **Optimum to threshold.** Given a routine that returns the best achievable value, answer any threshold question with one call: compare the returned optimum with `K`. 2. **Threshold to optimum.** Given a routine that answers yes or no, binary search on `K` between `0` and the total value of all parcels. With 200 parcels each worth at most 1,000,000, the total is at most 2 x 10^8, so about 28 calls pin the optimum exactly - and 28 is roughly the bit count of that total, which is polynomial in the instance's length. 3. **Optimum to the actual selection.** Fix parcels one at a time: ask whether the optimum is still reachable with a given parcel forced in, keep it if so, and repeat. That costs one pass of calls per parcel. Because the conversions are polynomial, a polynomial algorithm for either version would give one for the other. Neither is easier than the other in the sense that matters. ## NP-complete versus NP-hard, for the same requirement | version | what it asks | short yes-certificate | classification | |---|---|---|---| | decision | is some load within `C` worth at least `K`? | the chosen subset | NP-complete | | optimisation | what is the greatest value within `C`? | none - the answer is a number, not a yes | NP-hard, not in NP as stated | | construction | which parcels achieve that value? | the subset, once you know the value to beat | at least as hard as the other two | The row to take seriously is the middle one. Calling the optimisation version NP-complete is a common slip in interviews and in writing. **Complete** requires membership in the class, and a problem that returns a number is not a member of a class of yes-or-no problems. It is NP-hard: at least as hard as everything in NP. ## What this means when the requirement lands on your desk The practical payoff is that the shape of the requirement does not change the verdict. A product manager asking for the most valuable load, the cheapest set of containers, or the shortest tour is asking an optimisation question; the classification you look up is about the threshold version, and it transfers because of the two conversions above. It also tells you what a partial answer is worth. Any method that can only answer `can we reach K?` is already enough to find the optimum, at the price of a logarithmic number of repetitions. That is often how such a component is built in practice: a feasibility check wrapped in a search over the target. And it sets the register for the follow-up interviewers actually want. Once the decision version is on the table, the meaningful questions are about certificates, thresholds and what happens when the numbers grow - not about restating the business requirement in a more elegant way.

  • Why is the optimisation version called NP-hard rather than NP-complete?
    Completeness has two halves: hardness and membership in NP. NP is a class of yes-or-no problems, and the optimisation version answers with a number, so it cannot be a member however hard it is. It keeps the hardness half only.
  • How many calls to a threshold oracle does the binary search need, and why is that acceptable?
    About the bit count of the total value - roughly 28 calls when the total is 2 x 10^8. That count is logarithmic in a value, which is linear in the digits used to write it, so it stays polynomial in the instance's length.
  • Does a short certificate exist for a no answer to the threshold question?
    None is known. A yes is witnessed by one subset; a no asserts something about every subset, and exhibiting that cheaply would place the complement in NP too. The asymmetry between witnessing a yes and witnessing a no is deliberate in the definition.

saying these in an interview costs you the question

  • Calls the maximise-value version NP-complete
  • Says a decision version is a simplified or weaker problem
  • Claims the threshold form loses information the optimum carries
  • Thinks a certificate must also justify a no answer
  • Believes converting between the versions costs exponential work