What's the Difference? P, NP, NP-hard, and NP-complete Explained

(by Gemimi)

Here are the logical criteria for classifying computational problems into P, NP, NP-hard, and NP-complete.

These categories are fundamental in computational complexity theory, a field that blends pure mathematics (logic, computability) and theoretical computer science.1 They classify problems based on how their difficulty scales with the size of the input.2

The key concepts are:

  • Problem: A question to be answered, like "Is this number prime?"

  • Input Size ($n$): A measure of how much data the problem needs. For "Is this number prime?", $n$ would be the number of digits in the number.

  • Polynomial Time (Easy): An algorithm is "fast" or "efficient" if its runtime grows as a polynomial function of the input size 3$n$ (like 4$n^2$, 5$n^3$, or 6$n^{100}$).7 This is considered tractable.

  • Exponential Time (Hard): An algorithm is "slow" if its runtime grows exponentially (like $2^n$ or $n!$). This is considered intractable, as the runtime explodes even for moderately large $n$.

## Class P (Polynomial Time)

This is the class of "easy to solve" problems.8

  • Logical Criterion: A problem is in P if there exists an algorithm that can find its solution in polynomial time.9

  • In other words: If you double the input size, the time to solve it might increase by a fixed factor (like 4x, 8x, etc.), but it won't double for every new item you add.10

  • Example:

    • Sorting: Sorting a list of $n$ numbers can be done in $O(n \log n)$ time, which is faster than polynomial.

    • Primality Testing: Determining if an 11$n$-digit number is prime.12 This was famously proven to be in P in 2002.

##Class NP (Nondeterministic Polynomial Time)

This is the class of "easy to verify" problems.13

  • Logical Criterion: A problem is in NP if a proposed solution (a "certificate" or "witness") can be verified as correct or incorrect in polynomial time.14

  • Key Distinction: This does not say the problem is easy to solve. It only says that if someone gives you a potential answer, you can check it quickly.15

  • Example:

    • Subset Sum Problem: Given a set of integers, is there a non-empty subset that sums to zero?16

      • Solving (Hard): Finding this subset might require checking all $2^n$ possible subsets (exponential time).

      • Verifying (Easy): If someone hands you a subset, you can quickly add the numbers and check if the sum is zero (polynomial time).

  • Relationship to P: All problems in P are also in NP.17 If you can solve a problem quickly, you can certainly verify a solution quickly (by just solving it again and comparing the answers).18 This means $P \subseteq NP$.

  • The Big Question: The P vs NP problem, one of the Millennium Prize Problems, asks if 19$P = NP$.20 In other words, if a solution can be verified quickly, does that mean it can also be found quickly? Most mathematicians and computer scientists believe 21$P \neq NP$.22

##Class NP-hard (Nondeterministic Polynomial Hard)

This is the class of problems that are "at least as hard as the hardest problems in NP."23

  • Logical Criterion: A problem 24$H$ is NP-hard if every problem 25$L$ in NP can be reduced to 26$H$ in polynomial time (written 27$L \le_p H$).28

  • In other words: A "reduction" is a way to translate one problem into another. If you had a magic, super-fast algorithm to solve the NP-hard problem 29$H$, you could use it to solve every single problem in NP quickly.30

  • Important Note: An NP-hard problem does not have to be in NP.31 It can be harder than NP.32 It just has to be a "universal translator" for all NP problems.

  • Example:

    • The Halting Problem: Given a program and an input, will it ever stop running?33 This problem is undecidable (far harder than NP), but you can reduce NP problems to it. Thus, it's NP-hard but not in NP.

##Class NP-complete (Nondeterministic Polynomial Complete)

These are the "hardest problems in NP."

  • Logical Criterion: A problem is NP-complete if it meets two conditions:34

    1. It is in NP (its solutions can be verified quickly).35

    2. It is NP-hard (every other NP problem can be reduced to it).

  • In other words: NP-complete problems are the "sweet spot" of difficulty. They are in NP, but they are the hardest ones in that class.36 If you could find a polynomial-time solution for any single NP-complete problem, you would instantly have a fast solution for every NP problem, proving 37$P = NP$.38

  • Examples:

    • Satisfiability (SAT): Given a logical formula, is there an assignment of TRUE/FALSE values that makes the whole formula true? This was the first problem proven to be NP-complete.39

    • Traveling Salesman Problem (Decision Version): Given a list of cities and distances, can you complete a tour of all cities with a total distance less than $k$?

    • Subset Sum Problem: (This problem is also NP-complete).40

Summary of Criteria

Here's a simple table to organize the logical tests:

Class Can it be solved in polynomial time? Can a solution be verified in polynomial time? Can all NP problems be reduced to it?
P Yes Yes (Not a requirement)
NP (Unknown) Yes (Not a requirement)
NP-hard (Unknown) (Not a requirement) Yes
NP-complete (Unknown, but likely No) Yes Yes

This diagram shows the relationships, assuming $P \neq NP$ (which is widely believed).

  • P is a small circle inside the larger NP circle.

  • NP-complete is a set of problems inside NP.41

  • NP-hard is a large circle that completely contains NP-complete and also contains problems outside of NP.