P vs NP vs NP-Hard vs NP Complete - How to classify? - Dave Ishii

Problem Categorization Flowchart

Start with the problem you want to classify and follow these yes/no questions.

Can a proposed solution to your problem be verified as correct or incorrect in a reasonable (polynomial) amount of time?

YES 👉 The problem is in the class NP.
- This is the entry point for most common problems like Sudoku, Traveling Salesperson, etc. You can quickly check a finished puzzle or a proposed route.
- Now, proceed to Question 2.
NO 👉 The problem is NOT in NP.
- If you can't even check a solution quickly, it's in a different, often much harder, complexity class.
- Now, skip to Question 3 to see if it's NP-hard.

Can you devise an algorithm that solves the problem from scratch in a reasonable (polynomial) amount of time?

YES 👉 The problem is in the class P.
- Congratulations, you have an efficient algorithm! Problems in P are also, by definition, in NP.
- (This is the end of the line for this problem.)
NO (or "Nobody knows how") 👉 The problem is in NP but is not known to be in P.
- This is where things get interesting. The problem is easy to check but appears hard to solve.
- Now, proceed to Question 3.

Can every single problem in the entire class of NP be converted (or "reduced") into your problem in polynomial time?

YES 👉 Your problem is NP-hard.
- This means your problem is at least as hard as the hardest problems in NP.
- Now, look back at your answer to Question 1:
  - If you answered YES to Q1 (it's in NP) and YES to Q3 (it's NP-hard), then your problem is NP-Complete. This is the "gold standard" of computational hardness within NP.
  - If you answered NO to Q1 (not in NP) but YES to Q3 (it's NP-hard), your problem is NP-hard but not NP-complete. (Example: The Halting Problem, which is so hard you can't even verify solutions quickly).
NO 👉 Your problem is not NP-hard.
- Based on your previous answers, it is either:
  - In P (if you answered YES to Q2).
  - An NP problem that is not NP-complete (if you answered NO to Q2). These "intermediate" problems are thought to exist if P ≠ NP.

This diagram shows how the classes relate. Most computer scientists believe the two circles (P and NP) are not the same size.

P: The "easy to solve" problems.
NP: The "easy to verify" problems. P is a subset of NP.
NP-Complete: The hardest problems inside NP. If you solve one, you can solve them all.
NP-hard: Problems that are at least as hard as the hardest problems in NP. They don't necessarily have to be in NP themselves.

Here are the defining properties for each complexity class.

Solvable Quickly: A solution can be found in polynomial time (). This is its defining feature.
Tractable: Considered computationally "easy" or "efficient."
Verifiable Quickly: Since it can be solved quickly, a proposed solution can also be verified quickly.
Contained in NP: Every problem in P is also in NP.

Verifiable Quickly: A proposed solution can be checked for correctness in polynomial time. This is its defining feature. 🧐
"Hard to Solve": It's not known if these problems can be solved in polynomial time. Finding a solution may require trying an exponential number of possibilities.
Includes P: This class contains all problems from P.

This is a special subset of NP with two strict properties:

It must be in NP: A solution must be verifiable in polynomial time.
It must be NP-hard: Every other problem in NP can be converted (or "reduced") to it in polynomial time.

The Hardest in NP: These are the most difficult problems within the NP class.
The Key to P vs NP: If a polynomial-time solving algorithm is found for any single NP-complete problem, it would prove that P = NP. 🔑
Examples: The Traveling Salesperson Problem (TSP), Boolean Satisfiability (SAT), Sudoku.

This class is defined by a single property:

"At Least as Hard as NP": Every problem in NP can be reduced to it in polynomial time.

Not Necessarily in NP: An NP-hard problem does not have to be verifiable in polynomial time. It can be even harder than NP problems.
Includes NP-complete: All NP-complete problems are, by definition, also NP-hard.
Example (not in NP): The Halting Problem, which asks if a given program will ever stop running. There is no general algorithm to solve it, let alone verify a solution quickly.

Dave Ishii - Problem Solving Blog