让我们回到SAT。这个看似简单的问题的有趣特性是它不仅存在于NP中，而且还是NP完全问题。这里的“完整”一词与“图灵完整”中的完整相同。这意味着它是NP中最难的问题之一，但更重要的是这就是NP完全的定义 - NP中任何问题的输入都可以转换为SAT的等效输入，具体如下： 所有 NP 问题 L 都有一个在多项式时间可计算的”还原函数”f： L（x）= SAT（f（x）） 这样的一个还原函数不能被看成一个编译器：编译器是可以将一些编程语言写的源代码等价的转换成另一种编程语言的机器，也就是拥有语义行为的机器语言。因为 SAT 是 NP 完全的，所以这样一个还原对于任何可能的 NP 问题都是存在的，比如给定一个合适的块哈希，验证一笔
比特币交易是否合法。这里还可以将一笔交易转换成一个布尔函数的还原函数，因此当且仅当这个交易是合法的时候这个布尔函数就是可满足的。
版权申明：本内容来自于互联网，属第三方汇集推荐平台。本文的版权归原作者所有，文章言论不代表链门户的观点，链门户不承担任何法律责任。如有侵权请联系QQ：3341927519进行反馈。
