Is one difficult example enough to prove NP-completeness?

No. The property concerns an entire decision-problem family and requires the formal verification and reduction arguments.

Can a restricted version become easier?

Yes. Restrictions may exclude the structures needed by the general hardness proof.

Does an NP-completeness proof settle P versus NP?

No. It establishes that a polynomial-time solution to that problem would yield polynomial-time solutions throughout NP.

AI Glossary / Graphs and symbolic AI / Intermediate

NP-completeness

Definition

NP-completeness is the complexity-theoretic property of a decision problem that is both efficiently verifiable and at least as hard as every problem in NP under polynomial-time reductions. Proving this property usually involves showing membership in NP and reducing a known NP-complete problem to the problem being studied. The proof explains a general computational relationship, not the runtime of one example.

What it means

The adjective NP-complete labels a problem; NP-completeness names the property and the body of reasoning used to establish it. This distinction is useful when reviewing a claim: saying a task looks difficult is not a proof that it has this formal classification.

A valid claim must specify the exact decision problem, how inputs are encoded, and what counts as a yes answer. Small changes to restrictions can alter complexity. For example, general graph problems can become easier on particular graph families. A proof for an unrestricted problem does not automatically apply to every restricted business application of it.

How it works

First show that yes instances have certificates of polynomial length that a deterministic verifier checks in polynomial time. This establishes membership in NP. Then take a problem already known to be NP-complete and construct a polynomial-time transformation into the target problem.

The transformation must preserve answers in both directions: the original instance is a yes instance if and only if the transformed instance is a yes instance. It must work for all permitted instances, not just selected examples. Its output size and computation time must also be polynomial in the original input length.

These steps establish NP-hardness and membership in NP, hence NP-completeness. The reduction direction ensures that a fast solver for the target would solve the known hard problem. Reversing that direction can demonstrate an upper relationship without proving the desired hardness.

Three practical examples

Algorithm research: classify a newly formulated feasibility question before designing exact or approximate methods.
Technical review: check whether a claimed hardness proof establishes both verification and the correct reduction direction.
Product planning: distinguish inherent worst-case difficulty from implementation problems, while looking for useful restrictions on actual inputs.

Think of it this way

Think of building a translation that lets an expert in one puzzle language solve every puzzle written in another. To transfer difficulty, the translation must send the already hard puzzles into the new language and preserve their answers.

The analogy does not mean a few successful translations prove the general claim. The construction needs a rule for every allowed input, a correctness argument, and a bound on the effort and output size.

Worked example

Consider a standard relationship between CLIQUE and INDEPENDENT SET on simple undirected graphs. Given graph G and integer k, construct its complement: keep the same vertices, and connect two distinct vertices exactly when they were not connected in G. Keep k unchanged.

A set S is a clique in G exactly when every pair in S is connected in G. In the complement, those same pairs have no edges, so S is an independent set. Conversely, an independent set in the complement has every pair connected in G and is therefore a clique. This proves answer preservation in both directions.

For a concrete example, let G have vertices A,B,C,D and edges AB,AC,BC,CD. Its complement has edges AD and BD. The clique {A,B,C} in G becomes an independent set in the complement because none of AB,AC,BC is present there.

Constructing the complement requires examining at most n(n−1)/2 vertex pairs, so the transformation is polynomial. A proposed independent set can also be checked by inspecting its pairs. Given the established NP-completeness of CLIQUE, these arguments establish NP-completeness of general INDEPENDENT SET. The four-vertex example illustrates the construction; the general pairwise argument, not the example alone, supplies the proof.

Illustrative case study

Fictional case: a planning team reads that a broad allocation problem is NP-complete and assumes its own small restricted version must be equally difficult. A researcher examines the restrictions and finds that the available relationships form a special structure not covered by the hardness construction.

The team separates the unrestricted complexity claim from the algorithmic analysis of its actual input family. It still benchmarks realistic cases instead of assuming that a favorable classification guarantees low practical runtime. The fictional case illustrates precise use of theory, not a claimed new algorithm or theorem.

Common misconceptions and mistakes

A reduction from the target problem to SAT does not, by itself, prove that the target is NP-hard. Many easier problems can also be encoded as SAT. For a hardness proof, reduce a known hard problem into the target.

Showing only that certificates are easy to check establishes NP membership, not NP-completeness. Showing only hardness omits the membership condition. Both pieces matter.

Input encoding is another common trap. An algorithm polynomial in a numeric quantity may be exponential in the number of bits needed to write that quantity. Complexity analysis must use the actual input length rather than silently assuming unary-sized numbers.

Business use

NP-completeness helps explain why teams may need specialized solvers, restricted formulations, approximation, or time-limited search. It does not excuse missing benchmarks or justify declaring every slow implementation unavoidable.

When communicating a result, state the problem variant and the guarantee sought. An exact yes-or-no solver, a feasible-solution heuristic, and an optimizer returning a bound provide different services. A clear proof can guide strategy, while operational evaluation determines whether that strategy meets the project's needs.

Check your understanding

To prove a new problem B NP-hard using known NP-complete problem A, should the reduction map A to B or B to A?

Answer: A to B, so a solver for B could solve A through the transformation.

Related terms

NP-complete
NP-hardness
polynomial-time reduction
certificate
verifier
input encoding
decision problem
graph complement
independent set

Learn next

write the two directions of the clique-to-independent-set argument without relying on the small example. Then inspect another reduction and check its output size and input-encoding assumptions.

Sources

Cornell's reductions and NP-completeness handout explains proof structure, direction, certificates, and polynomial bounds: https://www.cs.cornell.edu/courses/cs4820/2013sp/Handouts/reductions.pdf

Cornell's introductory complexity material summarizes the class relationships: https://www.cs.cornell.edu/courses/cs2800/2015fa/lectures/lec36-np.html

The concrete complement graph and fictional planning review are original illustrations of standard complexity concepts.

Previous: NP-complete Next: NSynth