博文
多项式型与指数型算法悖论
|||
多项式型与指数型算法悖论
姜咏江
在P/NP问题的讨论中，很重要的概念就是O(nk)与O(2n)的时间复杂度问题。其实这是一条悖论！请看：
定理：任何有限个多项式相加仍然是一个多项式。
那么，n个元素集合的非空子集共有Cn1+Cn2+Cn3+…+ Cnn-1+ Cnn=2n-1个。毫无疑问，等式的左边是多项式型（因为任何一项都是一个多项式），而等式的右边是指数型。
请问，我们求子集过程的算法时间复杂度是O(nk)还是O(2n)？
2015-7-22
https://blog.sciencenet.cn/blog-340399-907226.html
上一篇：问题求解与验证的区别，答柳渝之质疑
下一篇：3-CNF一秒钟求出解
