45.NP完全性

title: 45. NP完全性 tags: zk complexity theory NP-completeness reduction SAT problem Cook-Levin theorem WTF zk 教程第 45 讲：NP完全性 在上一讲中，我们介绍了 P 类和 NP 类。这一讲，我们将深入探讨 NP 完全性的概念，这是复杂性理论中的一个核心主题，也是理解许多密码学和零知识证明系统的基础。 归约 在讨论 NP 完全性之前，我们需要先理解归约（Reduction）的概念。归约是将某个计算问题变换为另一个问题的过程，规约在复杂性理论中起着重要的作用，它允许我们比较问题的相对难度。 如果问题 A 可以转化为问题 B，那么我们就可以用 B 的答案去解决 A，也就是说 B 至少和 A 一样难。换句话说，如果我们能解决问题 B，就能解决问题 A。 根据可计算性理论，如果问题 A 可规约到问题 B，且问题 B 是可判定的，则问题 A 也是可判定的。等价地，如果问题 A 不可判定，且可规约到问题 B，则问题 B 也是不可判定的。 1.1 映射归约 映射归约（Mapping Reduct...