Course contentsShow
← Computer Science
Lesson 1888 of 2,87243. Complexity TheoryFree lesson

Introduction to Complexity Classes

Understanding what complexity classes are and why we categorize problems by their computational resource requirements.

Introduction to Complexity Classes

What you'll learn: You'll understand why we group computational problems by the resources they consume, not just whether they're solvable.

Beyond Decidability

You've learned that some problems are decidable (solvable by a Turing machine that always halts) while others are not. But knowing a problem can be solved isn't enough—we need to know how efficiently it can be solved. This is where complexity theory begins.

What Are Complexity Classes?

A complexity class is a collection of problems that can be solved using similar amounts of computational resources. These resources typically include:

  • Time: How many steps does the algorithm take?
  • Space: How much memory does it need?

Think of complexity classes like weight categories in boxing. Just because two fighters can both compete doesn't tell you much—knowing they're both in the "heavyweight" category gives you useful information about what to expect.

Why Categorize by Resources?

Some decidable problems can be solved in seconds; others would take longer than the age of the universe, even on the fastest supercomputer. For practical purposes, a problem requiring 10^100 years to solve might as well be undecidable.

Complexity classes let us:

  • Compare problems meaningfully (both solvable, but one is "easier")
  • Identify practical vs. impractical solutions
  • Understand fundamental limits on efficient computation
  • Make informed engineering trade-offs

For example, problems solvable in polynomial time (like sorting) versus exponential time (like certain optimization problems) fall into different classes, reflecting dramatically different practical feasibility.

Key Takeaway: Complexity classes organize problems by their resource requirements (time, space), helping us distinguish between problems that are theoretically solvable but practically different in difficulty.