3.21

Karp 规约

复杂度理论中的 Karp 规约，即多项式时间规约，相比可计算性理论中力大砖飞的图灵规约，显得更加精巧。为了 “多项式时间”，不能随意转化问题，而需要寻找两个问题结构之间巧妙的对应，然后给出恰到好处的构造。

证明 SAT 是 NP-complete 所用的规约是最有魅力的，但学过可计算性理论就不会对这个方法感到陌生：计算历史法（Computation History Method）。无非是之前用下推自动机甚至图灵机这样强大的计算模型验证计算历史，现在用 SAT 验证罢了。想到使用计算历史，这是本质思考；构造 SAT，这是技术细节。在图灵规约中，几乎只需要前者；Karp 规约中，技术细节却非常重要，本质思考和技术细节合在一起，造就了 Karp 规约的独特魅力。

在这里，需直面自己的智商。每一个问题都是全新的，没有既定的解题路径。大部分问题涉及的数学不会超过小学水平，只需要创造力和想象力。

学习进展

今天为止，Chapter 7 时间复杂度一章的习题才推了一半，这一半还是星号题比较少的那半，被自己蠢到。

所以学习进展完全崩了，还有三章没读，决定先跳过后半部分习题继续往后推 Chapter 8。

实际上 Chapter 6 就已经跳了不少习题，那时是因为寻找 Friedberg-Muchnik Theorem 的证明花了太多时间。幸运的是，Chapter 8 ~ 10 这最后三章习题都很少，没有劲爆尾杀。

最唐比