Defining NP-Hard and NP-Complete

(Directly answers the 7-mark subjective questions from 2022 Q7b, 2023 Q7b, and 2024 Q8a)

While P represents problems that are easy to solve, and NP represents problems that are easy to verify, we need a way to classify the absolute hardest problems in computer science.

Class NP-Hard (NPH)

A problem $H$ is considered NP-Hard if every problem in NP can be mathematically reduced to $H$ in polynomial time. In simple terms: An NP-Hard problem is at least as hard as the hardest problems in NP. Crucial Note: An NP-Hard problem does not have to be in NP. It might not even be verifiable in polynomial time, and it might be entirely undecidable (like the Halting Problem).

Class NP-Complete (NPC)

A problem is NP-Complete if it satisfies two strict requirements:

1. It is in NP (Its solutions can be verified in polynomial time).
2. It is NP-Hard (Every problem in NP reduces to it).

You can think of NP-Complete problems as the "hardest possible problems within the NP boundary." If anyone ever finds a fast, polynomial-time algorithm to solve just one NP-Complete problem, they will automatically have found a fast algorithm for every single problem in NP (proving $P = NP$). Examples include Boolean Satisfiability (SAT), Vertex Cover, and the Traveling Salesperson Problem.

The Relationship Diagram (Assuming $P \neq NP$)

To secure full marks on the exam, you must draw the Euler diagram that visually maps the relationship between these four classes.

Breaking down the relationships:

1. $P \subseteq NP$: Everything inside P is also inside NP.
2. $NPC = NP \cap NPH$: The NP-Complete boundary is the exact overlap where a problem is both inside NP and inside NP-Hard.
3. NP-Hard extends beyond NP: Some NP-Hard problems are so difficult that you can't even verify their solutions in polynomial time, placing them outside the NP bubble.