ReConcept Lab
English 中文
Graph connections

Draft

NP-Hardness

Understand why a problem is NP-hard when every problem in NP can reduce to it.

concept beginner complexityalgorithmsreductionsnp-hardness

Hook problem: start from the target hub

Imagine a target decision problem H and this condition:

if H is NP-hard, every efficiently checkable problem in NP should reduce to H with a polynomial-time reduction.

That means the question is not about one problem at all — it is about all of NP pointing into one target.

Hub first: target H receives reductions from many NP sourcesThese arrows are definition obligations, not built translations. They show required comparisons for NP-hardness.
decision problem Lsource instance xsource answer preserved
requiredL <=p Hall source decisions must map this waynot constructed here
HTarget decision problemQuestion: given y, is y in H?
Circuit-SATtiny circuit C with assignment 101target form: f_CircuitSAT(C)requires: x ∈ L ↔ f(x) ∈ HYes source → Yes target
SATformula φ = (x1 OR x2) AND (¬x1 OR x3)target form: f_SAT(φ)requires: x ∈ L ↔ f(x) ∈ HYes source → Yes target
CliqueG has a 3-cliquetarget form: f_Clique(G, 3)requires: x ∈ L ↔ f(x) ∈ HYes source → Yes target
Independent SetG with k = 4 where no size-4 independent set existstarget form: f_IS(G, 4)requires: x ∈ L ↔ f(x) ∈ HNo source → No target
Any L in NPabstract source instance xformal placeholder for ∀L in NPsymbolic only

The node on this page is a conditional definition target; no row here should be treated as an actual completed hardness proof.

The hub view shows where confusion starts: if rows are drawn, they are required translation obligations for the definition. It is not yet a completed hardness proof.

First naive idea

The word “hard” can sound intuitive:

  • Big inputs look hard.
  • Many candidates look hard.
  • Not finding a fast algorithm sounds hard.

These are motivations, but they are not enough to define NP-hardness.

Naive meanings of 'hard' that do not define NP-hard

Choose a card to see why each intuition fails the formal goal.

Big instance with big input sizeA giant-looking input is hard.

Hardness is not an input-size snapshot; it is a property of a decision problem family and reductions.

Too many candidatesIf brute force checks many candidates, the problem is NP-hard.
No known polynomial algorithmNo known fast algorithm proves NP-hard.

Where it breaks

NP-hardness is about the comparison relation. A single translation is a concrete example, but not the definition.

One reduction is a hint, not a definitionNP-hardness needs arrows from every source in NP, not one favorite source.
Invalid target vision
A <=p Hsingle source only
missing all other sources

This can show one concrete reduction example, but not NP-hardness.

Required NP-hardness viewL1 <=p HL2 <=p H..., forall L in NPcomplete family requirement
What fails in the one-source viewCannot conclude H absorbs all NP problems.Cannot trigger P=NP reasoning for arbitrary L.

For NP-hardness, one source row is only one witness hint, not full coverage.

Core invention: a universal quantifier over sources

To become a universal statement, we need a required family of reductions:

H is NP-hard⟺∀L∈NP,  L≤pH.H \text{ is NP-hard} \quad\Longleftrightarrow\quad \forall L \in NP,\; L \le_p H.

The contract is preservation:

x∈L⟺fL(x)∈Hx \in L \quad\Longleftrightarrow\quad f_L(x) \in H

For each row you need both directions, so both Yes and No are preserved.

Ledger: preserve both Yes and No answersIf reduction is valid for source instance x, the target instance f(x) must keep the same truth value.
Yes source instancetiny circuit C with assignment 101
ff_CircuitSAT(C)
Yes target instancetarget answer: Yes
No source instanceG with k = 4 where no size-4 independent set exists
ff_IS(G, 4)
No target instancetarget answer: No

Both yes and no rows satisfy the contract for the same reduction shape, preserving truth values.
Universal quantifier expands into many required source obligationsEach listed row is one required instance-preservation contract under the same target H.
Circuit-SATtiny circuit C with assignment 101source = Yestarget form: f_CircuitSAT(C)target = Yesif and only if (iff): x ∈ L ↔ f_L(x) ∈ H
SATformula φ = (x1 OR x2) AND (¬x1 OR x3)source = Yestarget form: f_SAT(φ)target = Yesif and only if (iff): x ∈ L ↔ f_L(x) ∈ H
CliqueG has a 3-cliquesource = Yestarget form: f_Clique(G, 3)target = Yesif and only if (iff): x ∈ L ↔ f_L(x) ∈ H
Independent SetG with k = 4 where no size-4 independent set existssource = Notarget form: f_IS(G, 4)target = Noif and only if (iff): x ∈ L ↔ f_L(x) ∈ H
Any L in NPabstract source instance xsource = Symbolictarget form: f_L(x)target = Symbolicif and only if (iff): x ∈ L ↔ f_L(x) ∈ H

Transitivity bridge for later proofs

Once a known NP-hard source A is available, you do not need to redraw all arrows to NP every time.

Transitivity bridge for practical proofsLater proofs often start with one known NP-hard source A, then show A <=p H.
Known premiseforall L in NP, L <=p AThis gives universal source coverage to A.
A <=p Hsingle transfer fact to prove
Combined conclusion∀ L in NP, L <=p HNo need to redraw all L at proof time.

From

∀L∈NP,  L≤pA\forall L \in NP,\; L \le_p A

and

A≤pHA \le_p H

you can infer

∀L∈NP,  L≤pH.\forall L \in NP,\; L \le_p H.

This is why many later hardness proofs only show one hard known source and one bridge reduction.

Solver implication pipeline

Read the flow conditionally: if H were in P, then every source L with a valid reduction would also be in P.

For each selected source:

function solveL(x: L) {
  const y = reduceLtoH(x);      // f_L(x)
  return solveH(y);              // assumed to be polynomial
}
Implication pipeline from an arbitrary chosen source

For any concrete source L with a valid reduction, this is the same five-step conditional flow.

1/5
Choose sourcePick source problem Circuit-SAT as the current L.Circuit-SAT preview source
Receive source instanceReceive instance x of Circuit-SAT.source: Yes
Reduce to HCompute and emit f_CircuitSAT(C). If the hardness definition is trusted, this step is valid for this source.target: Yes
Call solveHAssume the oracle for H runs in polynomial time. Call it on the translated target instance.target: Yesassumption: solveH ∈ P
Return source answerReturn the same Yes/No bit as target. Preservation means this is the correct answer for the original source instance.source: Yestarget: Yes

Pick source problem Circuit-SAT as the current L.

Choose sourcePick source problem Circuit-SAT as the current L.
Receive source instanceReceive instance x of Circuit-SAT.
Reduce to HCompute and emit f_CircuitSAT(C). If the hardness definition is trusted, this step is valid for this source.
Call solveHAssume the oracle for H runs in polynomial time. Call it on the translated target instance.
Return source answerReturn the same Yes/No bit as target. Preservation means this is the correct answer for the original source instance.

Correctness intuition

The last pipeline step is where correctness comes from the preservation contract:

  • Yes source instance says x in L; preservation gives f_L(x) in H; solver returns Yes.
  • No source instance says x notin L; preservation gives f_L(x) notin H; solver returns No.

So returning the target answer is safe only because the reduction preserves both truth values, not only one side.

Complexity consequence

The consequence formula is:

(∀L∈NP,  L≤pH)∧(H∈P)⟹NP⊆P.\left(\forall L \in NP,\; L \le_p H\right) \land \left(H \in P\right) \Longrightarrow NP \subseteq P.

With P ⊆ NP from P vs NP, we get:

P⊆NPandNP⊆P⟹P=NP.P \subseteq NP \quad\text{and}\quad NP \subseteq P \Longrightarrow P = NP.

This is a conditional implication. It does not prove P ≠ NP; it says “if one NP-hard target were in P, then all NP collapses to P.”

Composition cost stackThe reduction and H-solver costs compose, so polynomial stays polynomial.
symbolexpressionmeaning
mm <= n^btarget size bound
Treduce(n)O(n^a)translate source to H instance
TsolveH(m)O(m^c)solve H in polynomial time
Ttotal(n)O(n^a + n^{bc})combined pipeline
source size symbol: ntarget size symbol: mcombined: O(n^a + n^{bc})
Optional concrete samplen = 12Treduce(n) = O(12^a)m <= (12)^bTsolveH(m) = O((12^b)^c)Ttotal(n) = O(12^a) + O((12^b)^c)

NP-hard vs in NP vs NP-complete

NP-hardness is a comparison relation with source reduction obligations.

  • NP-hard does not automatically imply in NP.
  • NP-hard + in NP is the learner-facing NP-complete.
  • Optimization forms, and some outside classes, need separate conversion or separate models.
Class placement preview

A problem can be NP-hard without being in NP, and it can be in NP without being NP-hard.

NP-hard onlyin NP: No · NP-hard: Yes · NP-complete: NoHardness compares to all of NP, but membership in NP is not guaranteed.Possible relationship we keep as a concept preview.
In NP onlyin NP: Yes · NP-hard: No · NP-complete: NoEfficient certificates exist, but no universal reduction-from-all-NP evidence yet.Many verification-style problems are in NP but not known to be NP-hard.
NP-completein NP: Yes · NP-hard: Yes · NP-complete: YesIn NP and NP-hard at the same time.This is the standard strongest “hard and checkable” learner-facing badge.

Common confusions

Invalid claims to reject

These patterns look natural, but each fails the formal definition.

Wrong hardness arrow
conclusion: Reject: `H <=p L` does not establish `H` is NP-hard.

H <=p L does not prove H is NP-hard.

The claim `H <=p L` points in the wrong direction; hardness requires every L in NP to reduce to H.

This direction gives a reduction from H to L, so a solver for L (if any) would help solve H, not the other way around.

One source does not prove universal hardnessReveal why this is wrong
NP-hard does not imply in NPReveal why this is wrong
Hard because one instance is hugeReveal why this is wrong
No known fast algorithmReveal why this is wrong
Decision shortcut for optimization confusionReveal why this is wrong

Connections in the graph

This node sits after decision complexity and reductions:

p-vs-np -> polynomial-time-reductions -> np-hardness.

Later, concrete sources like Circuit-SAT will provide the first non-symbolic A <=p H proof chain.

Graph position and local flowThis follows the existing implementation edge sequence and previews future proof targets.
p-vs-npdecision problems + P/NP frame
->prerequisite
polynomial-time-reductionsdecision reductions
->prerequisite
np-hardnessuniversal target definition
->future preview
circuit-satfirst concrete source target

Exercises

Apply the node logic

Use each selected card to check direction, quantifier, and class membership claims.

If the claim is that `H` is NP-hard, which implication is valid?

Choose an answer to check this practice item.

A single row A <=p H is enough to declare H NP-hard.

Choose an answer to check this practice item.

Which class label matches this case? In NP and NP-hard are both true.

Choose an answer to check this practice item.

Assume H ∈ P and sat-preview has a valid reduction to H. What does the implication say for SAT?

Choose an answer to check this practice item.
  • Which arrow direction transfers hardness?
  • Why is one source row insufficient?
  • Which class labels combine to NP-complete?
  • What does H ∈ P imply for each source row?

Graph connections : NP-Hardness