高校问答足球彩票14场胜负17168:1.P与NP问题
来源：百度文库 编辑：高校问答 时间：2024/04/19 19:41:50
1.P与NP问题：一个问题称为是P的，如果它可以通过运行多项式次(即运行时间至多是输入量大小的多项式函数的一种算法获得解决，一个问题是NP的，如果所提出的解答可以用多项式次算法来检验。P等于NP吗?
你的定义有问题:如果一个问题可以在多项式时间内被确定机解决,则它属于P类问题；如果它可以在多项式时间内被非确定机解决，则它属于NP类问题。显然P是NP的子集。但是是否存在在NP中却不在P中的问题的问题是计算理论目前最著名的难题之一，还未得到证明，不过有无数迹象表明P很可能不等于NP。