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

The Class P: Polynomial Time

Define P as the set of decision problems solvable by deterministic algorithms in polynomial time.

The Class P: Polynomial Time

What You'll Learn

You'll understand what the complexity class P represents and why polynomial-time algorithms are considered "efficient" in computer science.

What is the Class P?

The class P (short for "Polynomial Time") is the set of all decision problems that can be solved by a deterministic algorithm in polynomial time.

In simpler terms: if you can write an algorithm that always gives a correct yes/no answer, and the number of steps it takes grows no faster than some polynomial function of the input size n (like n², n³, or n¹⁰⁰), then that problem belongs to P.

Why Polynomial Time?

Think of polynomial time as the dividing line between "practical" and "impractical" algorithms:

  • Polynomial algorithms (in P): O(n), O(n²), O(n³), O(n log n)
  • Exponential algorithms (not in P): O(2ⁿ), O(n!)

A problem with input size 1000 might take:

  • n² steps: 1,000,000 operations (feasible)
  • 2ⁿ steps: more operations than atoms in the universe (infeasible)

The Formal Definition

A decision problem L is in P if there exists a deterministic Turing machine that:

  1. Decides L (always halts with accept/reject)
  2. Runs in time O(nᵏ) for some constant k, where n is the input length

Analogy

Think of P as the "reasonable tasks" club. If you can guarantee finishing a task where doubling the problem size only multiplies your work by some fixed power (not doubles it exponentially), you're in the club.

Key Takeaway: The class P contains all decision problems solvable by deterministic algorithms in polynomial time, representing problems we consider computationally tractable and efficiently solvable.