---
title: "NP-hard and NP-complete problems"
subject: "Theory of Computation"
chapter: 6
key: "semester_3/theory_of_computation:np-hard-np-complete"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/np-hard-np-complete
site: BCT Engineering
---

# NP-hard and NP-complete problems

Theory of Computation · Chapter 6: Computational Complexity

- Asked in: 2072 Chaitra; 2073 Chaitra (asked 2 times)
- Video: [NP completeness (P, NP and NPC) Polynomial, Non-Polynomial, NP-Complete and NP hard algorithms](https://www.youtube.com/watch?v=19ryrsQIq3o) — Helping Tutorials
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/np-hard-np-complete
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-6

## Question

Explain NP-hard and NP-complete problems.

## Short answer

NP-hard problems are those to which every NP problem is polynomial-time reducible; they are at least as hard as NP. NP-complete problems are NP-hard problems that also belong to NP. Examples: SAT is NP-complete; if any NP-complete problem is in P, then P=NP. NP-hard includes problems outside NP, like the halting problem.

## Answer

#### Background
- **P:** decision problems solvable in polynomial time by a deterministic TM.
- **NP:** decision problems whose "yes" answers can be **verified** in polynomial time (equivalently, solved in polynomial time by a non-deterministic TM).
- A problem A is **polynomial-time reducible** to B (A ≤p B) if there is a polynomial-time computable f with w ∈ A ⇔ f(w) ∈ B.

#### NP-hard
A problem B is **NP-hard** if **every problem in NP** reduces to B in polynomial time. So B is at least as hard as every problem in NP. An NP-hard problem need **not** be in NP, and need not be a decision problem.

Examples: the halting problem (undecidable, so not in NP), the optimisation version of the travelling salesman problem.

#### NP-complete
A problem B is **NP-complete** if
1. B ∈ NP, and
2. B is NP-hard.

So NPC = NP ∩ NP-hard. These are the hardest problems in NP.

```text
   Assuming P ≠ NP:
   ┌───────────── NP ──────────────┐
   │                               │
   │  ┌─────┐          ┌───────────┼─────────────┐
   │  │  P  │          │    NP-    │             │
   │  └─────┘          │  complete │   NP-hard   │
   │                   │           │  (not in NP)│
   └───────────────────┼───────────┘             │
                       └─────────────────────────┘
   NP-complete = the overlap of NP and NP-hard
```

**Cook–Levin theorem:** SAT (satisfiability of Boolean formulas) is NP-complete. Other problems are shown NP-complete by reducing a known NP-complete problem to them (SAT ≤p 3-SAT ≤p CLIQUE, Vertex Cover, Hamiltonian cycle, Subset Sum, and so on).

#### Why it matters
If any one NP-complete problem has a polynomial-time algorithm, then **every** problem in NP does, so P = NP. Since no one has found such an algorithm, NP-completeness is taken as strong evidence that a problem is intractable, and approximation or heuristic methods are used instead.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. When is a problem B NP-hard?
   A. When B is in NP and solvable in polynomial time
   B. When B is in NP and has a short certificate
   C. When every problem in NP reduces to B in polynomial time
   D. When B is undecidable
   Answer: C. NP-hard means every NP problem polynomial-time reduces to B, so B is at least as hard as all of NP. B need not itself be in NP. (Key point: NP-hard definition)

2. Which is an example showing an NP-hard problem need not be in NP?
   A. Sorting
   B. The halting problem, which is undecidable
   C. Two-colouring a graph
   D. Checking if a graph is connected
   Answer: B. The halting problem is NP-hard but undecidable, so it is not in NP. (Key point: NP-hard need not be in NP)

3. What two conditions make B NP-complete?
   A. B is in P and B is NP-hard
   B. B is in NP and B is undecidable
   C. B is in NP and B is NP-hard
   D. B is NP-hard and not in NP
   Answer: C. NPC = NP ∩ NP-hard: the hardest problems that are still in NP. (Key point: NP-complete definition)

4. Why is finding a polynomial algorithm for one NP-complete problem so significant?
   A. It would only solve that one problem
   B. It would make every problem in NP polynomial-time solvable, so P = NP
   C. It would prove P ≠ NP
   D. It would make the halting problem decidable
   Answer: B. Every NP problem reduces to it in polynomial time, so a fast algorithm for one gives a fast algorithm for all, implying P = NP. The first NP-complete problem was shown to be SAT (Cook-Levin). (Key point: Consequence of NP-completeness)

## Related in Theory of Computation

- [Class P, class NP and NP-complete](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aclass-p-np-relation) — Theory of Computation, chapter 6