4.3 P, NP, and Reductions: Can We Compute It Within a Budget?

Undecidable problems don't cover all difficult tasks. Register allocation, instruction scheduling, and combinatorial optimization often have exhaustive algorithms, so they're decidable; the real trouble lies in the rapid growth of candidate solutions with input size, which can put exact optimization beyond the available time budget.

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 exact algorithms for restricted cases.

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, a positive integer $N$ has binary encoding length $\lfloor {\log }_{2}N\rfloor +1$. 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\ge 1}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 is in NP if it has a polynomial-time verifier such that every yes instance has an accepted certificate of polynomially bounded length, while no no instance has an accepted certificate. The bound is polynomial in the instance length. Without the no-instance condition, a verifier that accepts everything would slip through.

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, consider the decision version of the traveling salesman problem:

Input: a graph with nonnegative integer edge weights and threshold K, all encoded in binary
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. Checking that each vertex is visited exactly once, that each route edge exists, and that the total weight meets the threshold 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⟺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:

1. Provide a polynomial-time verifier to prove it is in NP;
2. Reduce a known NP-complete problem to the new problem to establish NP-hardness.

Proving that "it reduces to SAT" only shows it's not harder than SAT; it doesn't prove it's NP-hard.

5. Why SAT Is Central

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. Combinatorial Problems in Compilers

Register Allocation

An interference graph represents conflicts between variable live ranges. Idealized $k$-register feasibility becomes graph $k$-coloring. For general graphs, fixed $k\ge 3$ gives an NP-complete decision problem; $k=2$ is solvable by checking bipartiteness. Compilers use simplification, coalescing, spilling heuristics, or linear scan.

Not every interference graph is an interval graph. If the model truly consists of intervals on one line, interval-graph coloring is polynomial. General control-flow live ranges and machine constraints require separate treatment.

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: use treewidth, 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 best feasible solution found before timeout. If none was found, report that fact; it does not prove infeasibility.

NP-hardness does not require random guessing. Input structure, instance size, and the required solution quality determine the method.

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 "not polynomial": 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: Algorithms in P can still differ in their fixed polynomial degree, constants, and hardware costs.

References

• Clay Mathematics Institute: P vs NP

Practice

1. Rewrite "find a largest clique" as a decision problem and specify a certificate.
2. When proving that problem $B$ is NP-complete, the reduction should go from a known hard problem to $B$, not the other way around.
3. Propose a heuristic for choosing which values to spill when registers are scarce, and describe cases where it might fail.
4. Give 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 using 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.