这个说法其实我用了很久了，最近看到 这个知乎回答 下的一条评论，觉得可以记下来。
那个知乎问题是问：能不能不用递推式，直接用 Catalan 数的通项公式 得出 Catalan 数列的普通幂级数生成函数 这个回答是直接验算右边的幂级数展开正好是 Catalan 数的通项。底下有个评论说这是“NP 问题思维解法”。
这个说法很准确，很多时候一个解法看起来非常巧妙，是因为解题过程里的思维被隐藏起来了，单纯阅读答案会觉得这个解简直是从 non-determinism 里自己蹦出来的。然而，更有价值的是寻找 witness 的方法，而不是 witness 本身。如果说 witness 是“鱼”，则寻找 witness 的思路（最好是一个 RP 算法）是“渔”；如果说 witness 是“然”，那么寻找 witness 的思路是“所以然”。（后面这个比喻其实不太好，因为 witness 本身就是“所以然”，而判定结果才是“然”。）
下面讲几个记忆碎片。
十一学校的考试
我觉得我最初运用这种答题方法应该是小学时参加十一学校的考试。有一个题目是（对于当时的我来说）很复杂的一个应用题，该题还特别要求“用算术法解”（用设置“单位一”的方法求解）。当时我已经学会了字母表示数和方程的思想，自然不喜欢“算术法”。对于我来说，算术解法是高度 non-deterministic 的，而设未知数、列方程、解方程比巧妙地设置“单位一”要 deterministic 很多。于是我做了这么一件事：在草稿纸上用方程求解该问题，然后盯着求解过程编一个算术法的过程（大概就是把解方程的过程反过来写）。好在该题目只要求列出算式，不要求给每个步骤安上一个含义，所以我应该是顺利得分了。没想到我小学就深谙此道了！
抄可能有错误的答案 很多学生都有抄答案的经历，我也一样；很多学生都有抄答案但答案有错被老师发现的经历，我也一样。那么，如何继续在很短时间做完作业呢？我曾经用过的一个方法是检查答案并抄答案。如果说解题是决定一个 NP 问题，那么验证答案是可以在 P 内完成的。现在假设用最笨的方法去决定这个 NP 问题，也就是枚举所有可能的 non-deterministic choices，这需要很长时间。但如果假设我们有一个（接近正确的）答案，那么它提供了很多关于 non-deterministic choices 的信息，这使得回溯的次数大大减少。另外，不同于一般的 NP 问题，作业答案是可以验证部分正确性的，并且第一次出错之后，参考答案仍然可以提供很多关于修正之后如何选择 non-deterministic transitions 的启发。
“注意到”和姚家燕的“草稿” 很多数学题的解答都会用“注意到”，我印象最深刻的莫过于初等数学中的一些巧妙的不等式证明，开篇一个“注意到”，然后就扔进来一个超级大的恒等式，代入之后又进行一通狂算就得到了结果（陈计尤其擅长这个）。另一个例子是微积分的初学者对于证明中的 的选择可能会感到惊奇，典型的例子是 Toeplitz 定理以及 Stolz–Cesàro 定理（即数列的 L’Hôpital 定理）的证明。姚家燕教授告诉我们这个选择在打了草稿之后就很自然了。通常来说，解一个思路不是很确定的题目的时候，我们会在草稿纸上发散思维，直到遇到解，然后把到达解的路径搬到答卷上——这正是为什么答卷上只会看到完美的答案的原因。
我的导师对我的批评 我的导师 Lin 在我对她演示一些归约的时候表示我的讲法实在是太机械了，经常只是在带着她验证一个形式化的证明过程，而不是告诉她为什么要这么做。翻译成这里的话，就是说我应该展示思维是如何到达这个 NP witness 的，而不是展示 witness 本身。
我的导师对于一些思路的描述 我和我导师交流的过程中，发现她也会使用 non-deterministic 描述一些神奇的思路，例如在 Goldreich–Levin hardcore predicate 构造的证明中，想到使用猜测对数多个 bit 的方法来做证明，就是一个比较 non-deterministic 的例子。又例如我们最近的一个工作中，使用一个模块化的抽象可以让很多事情自然很多，也就是让推导过程看起来更加 deterministic。
请启用 JavaScript 来查看由 Disqus 驱动的评论。