最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 当计算机无能为力的时候,P对NP问题却不是这样

    计算机无能为力时的 P 与 NP 问题

    2000年5月,在克莱数学研究所公布的七个千年问题中,P vs NP问题是最有可能被普通人解决的。他可能非常年轻,在数学界不为人知,甚至接受过正规的数学训练。

    其他千年问题深埋在数学的深处,但 P 与 NP 问题并非如此。

    它主要考虑计算机执行某些任务的效率。这个问题不仅相对容易理解,而且解决它所需要的只是一个新奇的好主意,只需要你的想象力。

    下面我会详细解释,相信大家都能理解。

    P-to-NP问题也称为NP完全问题,其中P问题(多项式过程问题)是指计算机能够在有效时间内处理的问题,NP问题是指计算机能够在有效时间内处理的问题。可以在有效时间内验证。

    例如,已经证明的费马大定理就是一个P型问题。因为它的证明过程只有几百页,足以让一台计算机在有效时间内完成。

    但在给出证明之前,没有人知道需要多长时间或是否可以证明。

    这个千年难题需要解决的是“P是否等于NP”?

    解决一个问题需要多少步骤

    当今社会,计算机主要用于信息传播。但这并不是发明计算机的初衷。就像它的名字一样,计算机主要用于计算,其“可计算性”在数学上也有成熟的理论体系。这种可计算性理论远远早于今天的计算机技术。

    早在 1930 年代,一些数学家就开始独立研究“可计算性”的概念。

    他们只想知道哪些自然数到自然数函数是可计算的。

    例如,您需要到几个不同的城市出差。如果要提前规划好路线,就需要找到这些城市组合的最短路线和时间。显然,这个问题的关键在于城市的数量。面对这个问题,当然可以手动计算最优路线。

    但是如果数量很大np完全问题在生活中的应用,我们首先需要考虑的是找到一种方法来衡量在单台计算机上执行给定任务需要多长时间。

    问题的数据越多,我们计算它的时间就越长。

    简单来说,多项式时间过程是计算机可以有效处理的过程。

    所有算术运算——加、减、乘、除——都是多项式时间过程。

    多项式时间过程是多项式表达式(例如 CN、CN^2 或 CN^K)是时间复杂度的函数的过程。

    如果 C 和 K 都很大!比如5000的10000次方,那么这个过程即使要花费很多恒星的寿命也不够。

    但是,日常生活中产生多项式时间过程的C和K值是完全适中的,一般都是个位数,因此可以在短时间内被计算机高效处理。

    虽然指数时间过程比多项式时间过程增加得更多,但它们的分类过于粗略,意识到这一点的数学家开始寻找中间尺度的过程复杂性。

    他们发现,对于绝大多数指数时间过程来说,困难不是来自复杂的计算,而是来自极其简单的计算。

    使这个问题几乎无法解决的是需要验证的大量数据,因此完成整个过程所需的时间长得令人沮丧。

    为了将这一过程与另一个非常复杂的计算区分开来,数学家们提出了第三种过程:

    “非确定多项式时间过程”,即NP过程。

    我们知道计算机是确定性地工作的——它们按照预定的程序工作。因此,这里所说的“非确定性”基本上与当前的计算无关。

    下面是它的大致思路。

    假设您有一台计算机,它在计算的某个阶段总是从许多替代数字中做出最佳选择,那么它可以在多项式时间内解决这个问题。

    因为每个随机选择都是正确的一步,我们避免了数量惊人的可能性。

    一般计算机可以在多项式时间内解决的问题称为 P 型问题。但如果这是一个非确定性计算机在多项式时间内解决的问题np完全问题在生活中的应用,那么它就是 NP 类型的。

    从前面的理解很容易知道,NP问题介于P问题(多项式时间问题)和指数时间问题之间。

    NP 概念纯粹是理论上的,因为它基于当前不切实际的想法,即非确定性计算机将始终随机选择正确的步骤。然而,它显示出极大的重要性。

    工业和管理中出现的许多指数时间问题属于 NP 类型。如前所述,它们难以计算的原因仅仅是因为数据太大,以至于需要在基本相同的条件下重复相对容易的计算。

    显然,每一个P型问题都是NP问题,但是绝大多数NP问题不能证明是P问题

    需要注意的是,这个问题必须证明所有的NP问题都是P问题!

    相反,许多数学家应该更愿意证明 NP 不等于 P

    因为只需要一个反例。

    即:找到一个 NP 问题,证明它一定不能由计算机在多项式时间内解决。

    到 1971 年,库克在他的著名论文中给出了 NP 分类很重要的两个原因。

    他证明了有一个特殊的 NP 问题具有一个奇怪的性质:如果这个特殊问题可以用多项式时间过程来解决,那么其他 NP 问题也可以!

    库克将这个奇怪的属性命名为 NP-completeness。

    根据库克的定义,对于一个 NP 问题,如果找到一个可以解决它的多项式时间过程,也就是说 NP 类中的每一个问题都可以在一个多项式时间内解决,那么这个问题就是 NP 完全的。

    目前还没有人知道 RSA(互联网)加密系统的解码问题是否是 NP 完全的(很可能不是),因此可以在不证明 P 与 NP 相同的情况下开发该问题的多项式解决方案。在这种情况下,整个互联网安全系统将变得极其不可靠,足以说明P=NP的含金量有多高。

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 当计算机无能为力的时候,P对NP问题却不是这样

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论