Reductions and NP-completeness

Use finite binary encodings and deterministic polynomial time as the baseline model. P contains decision problems with polynomial-time algorithms. NP contains decision problems whose yes instances have certificates of polynomial length that a deterministic verifier checks in polynomial time; for a no instance, no certificate is accepted. Guessing a certificate and checking it motivates the letter N through nondeterminism, not through the phrase nonpolynomial. Every problem in P is in NP by ignoring the certificate.

For vertex cover, the decision instance is a finite simple graph and an integer budget k. A certificate lists at most k vertices, and a verifier checks that every edge touches the list. With a suitable membership representation, checking takes polynomial time in the explicit graph encoding. This proves membership in NP, not hardness. An optimization problem asking for the smallest cover is related but has a different output specification; NP-complete is formally a classification of decision problems here.

If A reduces to B and B has a polynomial-time decision algorithm, composing the construction with that solver gives one for A. Thus to prove B hard, start from a known hard A and build B instances. Reducing B to an easy or hard problem in the other direction gives an upper-bound relation instead and does not establish the intended hardness. Composition also requires polynomial output length; a construction that prints an exponentially large graph is not polynomial simply because each printed edge is easy to describe.

A problem is NP-hard if every NP decision problem reduces to it under the chosen reduction. It is NP-complete if it is additionally in NP. Starting from the Cook–Levin theorem that satisfiability is NP-complete, chains of proved reductions establish many others. In this lesson, use the established NP-completeness of Independent Set as the source and prove its simple translation to Vertex Cover. Proving a new link does not require reproving the entire foundational theorem each time, but the starting theorem must be stated rather than assumed invisible.

Given an Independent Set instance (G,k) with n vertices and a valid threshold from zero through n, output the Vertex Cover instance (G,n−k). The complement identity proves yes if and only if yes. The graph is unchanged and the threshold subtraction is polynomial in its encoded length. A cover verifier establishes target membership, so the known source hardness makes Vertex Cover NP-complete. Out-of-range thresholds can be resolved directly or mapped to fixed yes/no instances without affecting the result.

It remains unproved whether P equals NP. Therefore NP-completeness does not constitute an unconditional theorem that no polynomial-time algorithm exists. Under P ≠ NP, no deterministic polynomial-time exact decision algorithm solves all instances of an NP-complete problem. Some restricted graph families, parameter ranges, and individual instances can still be easy. Promise problems restrict allowed inputs explicitly; a reduction to such a problem must satisfy its promise on every produced instance. Ignoring that obligation can invalidate an otherwise plausible hardness argument.