P, NP, NP-hard, and NP-complete: Definitions and Relationships

In computational complexity theory, $P$, $NP$, $NP\text{-hard}$, and $NP\text{-complete}$ classify decision problems by how difficult they are to solve and/or verify. The key relationships are defined using polynomial time bounds and polynomial-time reductions.4

At a high level:

• keywordP are efficiently solvable.
• keywordNP are efficiently verifiable (equivalently, solvable by nondeterministic polynomial-time machines).
• keywordNP-hard are hardest (or beyond) the NP frontier; they may or may not lie in $NP$.
• keywordNP-complete are the hardest problems within $NP$: they are in $NP$ and NP-hard.

Decision problems and polynomial-time reductions (the “glue”)

A decision problem asks a yes/no question for each input instance. Complexity class statements here are for decision problems.

To compare difficulty, we use keywordpolynomial-time many-one (Karp) reductions: $A \le_m^P B$ means we can convert inputs for $A$ into inputs for $B$ in polynomial time so that answers are preserved.2

This lets definitions like “$H$ is NP-hard” mean: if we could solve $H$ fast, we could solve every problem in $NP$ fast too (via reduction).

1) Class $P$

Definition. $[keyword]def=\mathrm{"}P:decisionproblemssolvablebyadeterministicTuringmachineinpolynomialtime\mathrm{"}P$keywordP is the class of decision problems solvable in deterministic polynomial time.

Formally: a language/problem is in $P$ if there exists a deterministic algorithm that decides it using time $n^{O(1)}$ (polynomial in input length).

Implication: If a problem is in $P$, then both finding and verifying solutions are efficient (because solving is efficient).

Key terms (for this block): keyworddecision problem, keyworddeterministic, keywordpolynomial time, keywordtime complexity.

2) Class $NP$

There are two equivalent standard characterizations:

1. Nondeterministic view: $[keyword]def=\mathrm{"}NP:decisionproblemssolvablebyanondeterministicTuringmachineinpolynomialtime\mathrm{"}NP$keywordNP is the class of decision problems decidable by a nondeterministic Turing machine in polynomial time.2

2. Verifier/certificate view: $[keyword]def=\mathrm{"}NP:problemswhereayes-instancehasapolynomial-timeverifiablecertificate\mathrm{"}NP$keywordNP is also the class of decision problems for which “yes” instances have polynomial-size certificates that can be verified in polynomial time by a deterministic verifier.2

That these are equivalent is standard (e.g., through correspondence between nondeterministic choices and certificates).

Relationship with $P$. Every problem in $P$ is also in $NP$ because if you can solve it in polynomial time, you can also verify a claimed solution in polynomial time.2

So: $P \subseteq NP$.2

Key terms (for this block): keywordcertificate, keywordverifier, keywordnondeterminism, keywordverification.

3) $NP\text{-hard}$

Definition. A problem (usually decision; can be more general) $H$ is keywordNP-hard if every problem in $NP$ reduces to $H$ in polynomial time.

Crucially:

• $H$ does not have to be in $NP$. It might not have efficiently checkable certificates (or might even be undecidable in broader settings), but it is still “at least as hard as” all of $NP$ under reductions.

Why reductions matter. If $L \in NP$ and $L \le_m^P H$, then a polynomial-time solver for $H$ would imply a polynomial-time solver for $L$ (by composing the reduction with the solver).2

Key terms (for this block): keywordhardness, keywordcomposition, keyworddifficulty order, keywordoutside-NP.

4) $NP\text{-complete}$

Definition. A problem $C$ is keywordNP-complete if:

1. $C \in NP$, and
2. $C$ is NP-hard.

So $NP$-complete problems are the “hardest” problems within $NP$: they are efficiently verifiable, but every other problem in $NP$ reduces to them in polynomial time.

Cook–Levin theorem (existence of NP-complete problems). A standard result states that Boolean satisfiability ($SAT$, and variants like $3SAT$) is NP-complete; equivalently, every problem in $NP$ reduces to satisfiability in polynomial time.

5) Relationship between $P$, $NP$, $NP\text{-hard}$, and $NP\text{-complete}$

The core inclusions are:

1. $P \subseteq NP$.2
2. $NP\text{-complete} \subseteq NP$ (by definition: NP-complete problems are in $NP$).
3. $NP\text{-complete} \subseteq NP\text{-hard}$ (again by definition: NP-complete problems are NP-hard).
4. $NP\text{-hard}$ is not necessarily a subset of $NP$ (NP-hard problems may lie outside $NP$).2

So we can write the clean set-theoretic relationship:

This is exactly the “in $NP$ and NP-hard” definition.

The big open question: $P$ vs $NP$

• If $P = NP$, then every problem in $NP$ becomes tractable, and many consequences follow.
• If there exists an NP-complete problem in $P$, then $P = NP$ (because NP-complete problems are NP-hard, so polynomial-time solvability would collapse the whole NP hierarchy to $P$).

This is why NP-completeness is central: NP-complete problems are the “borderline” of what might be solvable efficiently.