layout: post title: "用Python实现的NP完全性" description: "用Python实现的NP完全性" categories: [Python] tags: [python] redirect_from: /2018/09/29 NP完全性 之前学习过的算法都是多项式时间算法:对规模为n的输入,它们在最坏情况下的运行时间为O(n^k),其中k为某个常数 但是不是所有的问题都能在多项式时间内解决.例如图灵著名的“停机问题”,任何计算机不论耗费多少时间也不能解决 Github Code