Understanding Complexity Class P

1. The Line Between "Fast" and "Slow"

Your practical experience in software and AI development has likely given you an intuition for which algorithms are fast and which are slow. An algorithm that scales linearly with input size feels very different from one that requires checking every possible combination of inputs. Complexity theory formalizes this intuition by drawing a line between polynomial-time algorithms and exponential-time algorithms.

• Polynomial time: The running time is bounded by $O(n^k)$ for some constant $k$. Examples include $O(n)$, $O(n\log n)$, $O(n^2)$, and $O(n^{100})$.
• Exponential time: The running time grows as $O(c^n)$ for some constant $c>1$. Examples include $O(2^n)$ and $O(n!)$.

The difference in growth is not just academic; it has profound practical consequences.

As the reading highlights, even a massive increase in computing power barely makes a dent in the size of problems we can solve with an exponential-time algorithm. In contrast, polynomial-time algorithms scale much more gracefully. This distinction is the primary motivation for defining our first major complexity class.

2. Formal Definition of the Class P

We can now formalize this notion of "efficiently solvable" using the language of Turing Machines and time complexity.

First, let's be precise about what a polynomial-time algorithm is in this context.

Definition: Polynomial-Time Turing Machine
A deterministic Turing Machine $M$ is said to run in polynomial time if there exists a constant $k\ge 0$ such that its time complexity $t_M(n)$ is in $O(n^k)$.

With this, we can define the complexity class P.

As the video explained, the class P is the set of all languages that can be decided by a deterministic Turing Machine in polynomial time. Remember that for this module, we focus on decision problems—problems with a "yes" or "no" answer.

Definition: The Complexity Class P
The complexity class P is the set of all languages $L$ for which there exists a deterministic Turing Machine $M$ that decides $L$ in polynomial time.

Formally, we can express this as the union of all polynomial time-complexity classes:
$P={\bigcup }_{k\in \mathbb{N}}\text{TIME}(n^k)$

Here, $\text{TIME}(n^k)$ represents the set of all languages decidable by a deterministic TM in $O(n^k)$ time.

3. The Significance of P: Robustness and Closure

You might wonder why we use Turing Machines, which are quite abstract, and why polynomial time is the "right" boundary for tractability.

1. Robustness Across Models: A key insight in complexity theory is that most "reasonable" deterministic models of computation are polynomially equivalent. This means that a problem solvable in polynomial time on a Turing Machine is also solvable in polynomial time on a random-access machine (RAM), which more closely models a real computer, and vice-versa. This principle, sometimes called the Cobham-Edmonds thesis, gives us confidence that the class P is a fundamental property of problems, not just an artifact of the TM model. Your experience building complex systems in Python is based on a RAM model, and it's this equivalence that allows us to apply these theoretical results to practical computing.

2. Closure Under Composition: Polynomials have a nice closure property: if you substitute a polynomial into another polynomial, the result is still a polynomial. In programming terms, this means if you have a polynomial-time algorithm that makes calls to a polynomial-time subroutine, the overall algorithm remains polynomial-time. This aligns with how we build complex software from smaller, efficient modules.

4. Examples of Problems in P

To make the class P more concrete, let's look at a couple of important problems that belong to it.

The PATH Problem

One of the most fundamental graph problems is determining reachability.

Problem: PATH
Input: A directed graph $G=(V,E)$ and two vertices $s,t\in V$.
Question: Is there a directed path from $s$ to $t$ in $G$?

This problem is clearly in P. Algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS), which you've likely encountered in your studies, solve this efficiently. A BFS starting from $s$ will find $t$ if and only if a path exists. The running time of BFS is $O(|V|+|E|)$, which is a polynomial function of the size of the graph encoding.

All Context-Free Languages

In our earlier modules, we spent a lot of time on Context-Free Languages (CFLs). It turns out that the decision problem for any CFL—that is, "given a string $w$ and a CFG $G$, is $w\in L(G)$?"—is in P.

This is a powerful result, as it covers a vast and useful class of languages, including the syntax of most programming languages. The video you just watched also touches on this.

The algorithm mentioned, which runs in $O(n^3)$, is a variant of the CYK algorithm (Cocke-Younger-Kasami), which we will study in more detail later in the course. For now, the key takeaway is that deciding membership in any CFL is a tractable problem.

Conclusion

In this lesson, we transitioned from measuring time to classifying problems based on it. We established a formal definition for the class of problems considered "efficiently solvable."

Key Takeaways:

• A problem is considered tractable if there is a deterministic algorithm that solves it in polynomial time, i.e., with a time complexity of $O(n^k)$ for some constant $k$.
• The complexity class P is the set of all decision problems that can be solved by a deterministic Turing Machine in polynomial time.
• The choice of polynomial time as the threshold for tractability is robust because it is largely independent of the specific deterministic model of computation used (e.g., TM vs. a real computer).
• Many fundamental problems, such as PATH in graphs and membership in any context-free language, belong to the class P.

Preview of the Next Lesson:
We've now defined a class for problems we know how to solve efficiently. But what about problems like the Traveling Salesperson Problem or Circuit Satisfiability from our introductory reading, for which no polynomial-time algorithm is known? These problems have a different, fascinating property: while we can't seem to find a solution quickly, we can verify a proposed solution quickly. This leads us to our next major topic: the definition of the complexity class NP.