4.3 P, NP, and Reductions: After Computability, the Question Becomes, Can We Compute It in a Reasonable Time?
Undecidable problems don't cover all difficult tasks. Register allocation, instruction scheduling, and combination optimization often have exhaustive algorithms, so they're decidable; the real trouble lies in the rapid growth of candidate solutions with input size, making it impossible to compute the exact optimal solution in a timely manner.
Lesson Objectives
- Distinguish decidability from complexity;
- Define P and NP using decision problems;
- Distinguish NP-hard from NP-complete;
- Understand why compilers use heuristic, approximate, and bounded-precision algorithms.
1. Complexity must be defined with respect to input size first
Algorithm complexity describes how resources grow with the length of the input $n$. The input length is the number of encoded symbols or bits, not necessarily equal to the numerical value of the business object.
For example, the binary encoding length of an integer $N$ is approximately $\log_2 N$. An algorithm that runs for $N$ steps appears linear in terms of the value of $N$, but is exponential in terms of the number of input bits.
Complexity analysis also needs to indicate:
- Worst-case, average-case, or amortized analysis;
- Time or space;
- Computational models and fundamental operations;
- Are parameters included as part of the input.
2. P: Problems solvable in polynomial time
P is the class of languages decidable by a deterministic Turing machine in polynomial time relative to input size:
$$ P=\bigcup_{k\ge1}TIME(n^k). $$
P is often taken as a rough boundary for "theoretically feasible," but polynomial doesn't mean practically fast: $n^{100}$ is unacceptable, and even $n^3$ might be too slow for large inputs. Conversely, exponential algorithms can be entirely practical for small instances.
P's value lies in its robustness relative to computational models and constant factors, and its good closure under algorithmic combinations, not in a direct promise of production latency reduction.
3. NP: A certificate can be verified in polynomial time
A decision problem in NP satisfies: for every "yes" instance, there exists a certificate of polynomial length that can be verified by a deterministic algorithm in polynomial time.
Equivalently, NP is the class of languages decidable in polynomial time by a non-deterministic Turing machine. Here, "non-determinism" refers to a mathematical model, not a random algorithm.
For example, using the Traveling Salesman Judgment Version:
A weighted graph and a threshold K
Question: Does there exist a route that visits each vertex exactly once and returns to the starting point, with total weight ≤ K?A certificate is a candidate solution. Verifying that each vertex is visited exactly once and computing the total weight can be done in polynomial time.
The traveling salesman problem of finding the shortest route is an optimization problem. When discussing NP-complete problems, it's typically first converted into the corresponding decision version; the optimization version is often called NP-hard and can be connected through repeated decision checks or other techniques.
Clearly $P \subseteq NP$: if we can solve it quickly, we certainly can verify it quickly. Whether $P = NP$ remains an open question.
4. Polynomial-Time Reduction
If instances of problem $A$ can be polynomial-time transformed into instances of $B$ while preserving the answer:
$$ x\in A\iff f(x)\in B, $$
We write $A \le_p B$. If there is a polynomial-time algorithm for $B$, then we can first transform and then solve $A$.
- $B$ is NP-hard: every NP problem can be polynomially reduced to $B$;
- $B$ is NP-complete: $B$ is both in NP and NP-hard.
To prove a new problem is NP-complete, you typically need two parts:
- Provide a polynomial-time verifier to prove it is in NP;
- Reduce a known NP-complete problem to itself to prove NP-hard.
Proving that "it reduces to SAT" only shows it's not harder than SAT; it doesn't prove it's NP-hard.
Why the SAT is at the core of the process
The Boolean Satisfiability Problem (SAT) asks: does there exist an assignment of values to variables that makes a Boolean formula true? The Cook–Levin theorem proves that SAT is NP-complete: any polynomial-time verifiable process can be encoded into a Boolean formula of polynomial size.
SAT solvers perform very well on many real-world instances, but NP-completeness refers to the worst-case classification, which does not mean every instance is hard. Structured inputs, preprocessing, conflict learning, and heuristics for branching can solve large numbers of practical problems, though difficult instance families still exist.
6. Compiler Combination Difficulties
Register Allocation
After constructing a conflict graph from variable live intervals, ideal k-register allocation corresponds to k-coloring the graph. Since graph coloring is NP-complete in general, production compilers typically use graph simplification, merging, spilling heuristics, or linear scanning.
The real goals also include calling conventions, register classes, fixed registers, and instruction constraints, this isn't just a typical textbook diagram. Theoretical reductions reveal core difficulties, but engineering models remain far more complex.
Instruction Scheduling
Instructions must be scheduled under data dependencies, functional units, and latency constraints. Many general forms are NP-hard, and compilers use list scheduling, local search, or limited scheduling windows.
Instruction Selection and Optimization Combination
The local tree pattern can be efficiently selected using dynamic programming; however, with the addition of DAG sharing, complex machine constraints, and cross-block combinations, certain forms become more challenging. It's incorrect to broadly state that "code optimization is all NP-hard", instead, the problem definition and constraints must be clearly specified.
7. A Toolbox for Dealing with NP-hard Problems
- Limit problem structure: leverage tree width, interval graphs, or the structural properties of fixed-target architectures;
- Parameterized Algorithms: Perform $f(k)n^{O(1)}$ computations for small parameter $k$;
- Approximation Algorithm: Provides a provable gap from the optimal value;
- Heuristic: Pursues practical quality without a uniform worst-case guarantee;
- Exact Solvers: ILP, SAT, SMT, dynamic programming, or branch and bound;
- Hybrid Strategy: Exactly solve the hot path, use fast heuristics for the rest;
- Time Budget: Return the current best solution if timeout occurs.
“It’s wrong to conclude that ‘NP-hard means you can only guess randomly.’ The input structure, instance size, and target quality determine which method to use.”
8. Don't mix three boundaries together
| Question | Focus | Typical Conclusion |
|---|---|---|
| Computability | Whether there exists an algorithm that always provides an answer | Decidable / Undecidable |
| Complexity | How algorithm resources scale with input size | P, NP, PSPACE, etc. |
| Engineering Performance | Whether specific hardware and data meet the budget | Latency, Throughput, Memory, Power Consumption |
A problem may be decidable but have expensive worst-case complexity; it may belong to P yet be impractical due to large constants or scale; or it may have a theoretically bad worst case, but real-world instances are efficiently solved by good heuristics.
Common Misconceptions
- NP means "non-deterministic polynomial time": NP refers to problems that can be verified in polynomial time, not "not polynomial."
- NP-hard problems are all within NP: Optimization problems or even undecidable problems might be called at least NP-hard; only NP-complete problems require membership in NP.
- Being able to quickly verify numerical optimality is equivalent to being able to quickly verify candidate feasibility: A certificate of optimality might be more complex.
- P equals actual fast: The complexity class ignores constants, exponential factors, and hardware details.
Practice
- Rewrite "find a largest clique" as a decision problem and specify a certificate.
- When proving that problem $B$ is NP-complete, the reduction should go from a known hard problem to $B$, not the other way around.
- Propose a heuristic for handling overflow when register scarcity occurs, and describe cases where it might fail.
- An example of an algorithm that belongs to P but may still be expensive in practice.
Summary
Decidability asks whether an algorithm exists; complexity asks how resources grow. P means problems solvable in polynomial time, NP means problems whose "yes" answers can be verified in polynomial time; NP-complete problems are in NP and represent the full spectrum of NP difficulty. Compilers tackle combinatorial hardness by leveraging structure, approximation, heuristics, and exact solvers, rather than pursuing a nonexistent universal strategy.
The theoretical foundation here forms a complete staircase: finite state machines, stacks, Turing machines, undecidability, and complexity. The next chapter returns to the engineering reality, stably producing tokens from a character stream.