210
2023-12-17 04:34
adminP-NP I}}题(P-NP problem)亦称P=? NP问题，计算复杂性理论以及计算机理论中最重要的一个未解决问题。
它问在多项式时间界下，确定型图机接受的语言类是与非确定型图灵机所接受的语言类NP是否是相同的。
因为PcNP，所以，P-NP问题实际上是问这种包含关系是否是严格的，也即非确定型多项式时间算法是否确实比确定型多项式时间算法更有力。
但是，至目前为止，只知道当某个问题SENP时，一定存在一个多项式p和常数。，使S的确定型复杂性界为为。·2a<.,>.即S为指数时间可计算的.
顶一下
(0)
0%
踩一下
(0)
0%
- 相关评论
- 我要评论
-
上一篇：返回栏目
下一篇：bahamas是哪个国家？