layout: post title: "用Python实现的NP完全性" description: "用Python实现的NP完全性" categories: [Python] tags: [python] redirect_from:

• /2018/09/29

之前学习过的算法都是多项式时间算法:对规模为n的输入,它们在最坏情况下的运行时间为O(n^k),其中k为某个常数

但是不是所有的问题都能在多项式时间内解决.例如图灵著名的“停机问题”,任何计算机不论耗费多少时间也不能解决

Github Code