Skip to content
uencoder

NP-Completeness

An NP-complete problem belongs to NP and has every NP problem polynomially reducible to it; these are the hardest problems in NP.

Purpose

To understand the complexity hierarchy and recognize intractable problems.

Mechanism

NP: verifiable in polynomial time. NP-hard: every NP problem reduces to it. NPC=NP∩NP-hard. If any NPC problem has a polynomial solution, then P=NP. Classics: SAT, TSP, vertex cover.

Use cases

  • Complexity analysis
  • Problem hardness assessment
  • Reduction proofs

Related terms

Provable Security
Provable security reduces the security of a cryptographic scheme to a widely believed computationally hard problem: if a polynomial-time attacker breaks the scheme, a polynomial-time algorithm for the hard problem can be built.
GLOSSARY

References