多项式时间

先看一个麻烦

两个算法，都能解同一个问题。A 需要 n² 步，B 需要 2ⁿ 步。n 是输入的长度。

n = 10 时：A 要 100 步，B 要 1024 步。B 只慢十倍，看起来不算灾难。

n = 100 时：A 要 一万步，B 要 2¹⁰⁰ ≈ 10³⁰ 步。

这时候差别不再是”慢一些”。就算每秒算一万亿次，B 也要跑 10¹⁰ 年——比宇宙年龄长。而 A 在一毫秒内结束。

朴素判据，以及它为什么不够

朴素的想法是按”实际耗时”分类算法：能在一小时内跑完的算，跑不完的不算。

这个判据没法用，原因有两条。硬件会变快——今天跑一小时的，十年后跑一分钟，那分类就得重划。更要紧的是它没有说明增长的形状：上面那个例子里，真正决定命运的不是 n=10 时谁快，而是 n 变大时两者如何分道扬镳。

所以复杂度理论换了个问法：不问”要多久”，而问”输入长度每增加一点，代价怎么变”。

机制：分界线画在多项式与指数之间

如果一个算法的步数能被 n 的某个固定次幂控制住——n、n²、n³、n^100 都算——就称它是多项式时间的。所有存在多项式时间算法的问题构成复杂度类 P。

关键在”固定次幂”：指数是常数，不随 n 变。对比一下：

多项式：n, n², n³, n^100      ← 指数是常数
指数级：2ⁿ, 3ⁿ, n!            ← 指数含 n

为什么这条线画得有意义？因为多项式在两种运算下是封闭的：多项式的和、积仍是多项式；把一个多项式时间算法当子程序调用多项式次，总代价还是多项式。这让”可行”这个概念可以组合，而指数级不具备这个性质。

回访：n^100 真的算”可行”吗

不算。这是这个概念最诚实的一个弱点：n^100 在任何现实规模上都跑不完，但它在 P 里；而某些指数级算法（比如 SAT 求解器）在实践中飞快。

所以 P 是一条理论分界线，不是工程建议。它回答”这个问题原则上可解吗”，不回答”我今晚能跑完吗”。

《PRIMES is in P》正是这个区分的教科书案例：它证明素数判定属于 P，是重大的理论突破；但它给出的算法比工程上实际使用的 Miller-Rabin 慢几个数量级，至今没有密码库采用。理论边界移动了，工程实践没有变。

边界与常见误解

**P 不等于”快”。**它等于”随输入长度多项式增长”。n^100 是多项式，慢得没法用。

**不在 P 里不等于无解。**只是没有已知的多项式算法，或者已被证明不存在。这两种情况差别很大。

**P vs NP 问的不是这个。**P 是”能快速求解”，NP 是”给了答案能快速验证”。两者是否相等是悬赏百万美元的未解问题。