Skip to main content

Concept quiz

  1. Does NP mean “not polynomial”? Explain using P contained in NP.
  2. If A≤pB, which solver would let you solve the other problem?
  3. What extra evidence distinguishes a feasible cover from an optimal cover?
  4. Why does maximal matching suffice for the factor-two proof?
  5. Why is a teaching size limit not a complexity lower bound?
  6. Which part of the approximation argument fails with vertex weights?

Calibration: NP is polynomially verifiable yes-certificates; a B solver solves A; a tight lower bound or completed exact proof establishes optimality; no edge remains between unmatched endpoints; limits constrain this implementation; endpoint count does not bound total weight. Give examples rather than only repeating these phrases.