Back to course

Lesson 57: Introduction to Complexity Classes: P vs. NP

Algorithms: From Zero to Hero (A Beginner's Guide)

57. Introduction to Complexity Classes: P vs. NP

Complexity classes categorize computational problems based on the resources required to solve them. This is crucial for understanding the limits of computation.

P Class (Polynomial Time)

P stands for 'Polynomial time.' This class includes all decision problems (problems with a yes/no answer) that can be solved by a deterministic Turing machine (i.e., a standard computer) in polynomial time, meaning O(N^k) for some constant k.

  • Examples: Sorting, searching, finding the MST.

NP Class (Non-deterministic Polynomial Time)

NP includes all decision problems whose solution can be verified in polynomial time. Note: NP does NOT mean 'Non-Polynomial'.

  • If someone hands you a potential solution to an NP problem, you can quickly check if it's correct.
  • Example: The Traveling Salesperson Problem (TSP). Finding the shortest route is hard, but verifying that a proposed route is shorter than X is easy.

The P vs. NP Problem (The Million Dollar Question)

Does P = NP? Can every problem whose solution is quick to verify also be quick to solve? Most computer scientists believe P ≠ NP, but this remains unproven. The NP-Complete problems are the 'hardest' problems in NP.