老师：

“你们天天抱怨作业多、写作业累，我每天要给全班几十个人批改作业，一本一本地看，一道一道地改。你们只需要写自己的一份，我却要改几十份，难道我就不累吗？”

学生：

老师，您说改作业很累，但从计算复杂性理论的角度来看，我认为有必要区分求解问题与验证答案的时间复杂度。

假设我们面对的是一类 NP 完全问题。

学生做作业，本质上是在寻找问题的解。在没有已知多项式时间算法的情况下，朴素穷举可能需要 O(2^n) 的指数时间。

而老师改作业，本质上是在验证学生提交的候选解。对于 NP 问题，给定合适的解及其证书，验证过程可以在 O(n^k) 的多项式时间内完成，其中 k 为常数。

请注意：我们的 n 在指数上，您的 n 在底数上。

即使您需要批改全班几十份作业，也不过是给多项式时间复杂度乘上一个常数因子，并不会改变其复杂度类别。

当 n 趋于无穷时，指数函数 2^n 的增长速度超过任何固定次数的多项式函数 n^k，两者存在根本性的渐近增长差异。

所以，您如果认为做作业和改作业在计算复杂度上没有本质区别，那么我建议您先研究一下，能否为任意一个 NP 完全问题构造出多项式时间求解算法。

因为一旦成功，您就证明了 P=NP。

到时候您不仅不用改作业了，还能去克雷数学研究所领取一百万美元奖金。