裁决中的P与NP以及复杂性的复杂度

AIGC动态欢迎阅读

原标题：裁决中的P与NP以及复杂性的复杂度
关键字：问题,复杂度,函数,数学,电路
文章来源：大数据文摘
内容字数：0字

内容摘要：

作者：Benjamin Skuse
译者：zzllrr小乐
如果我请你出庭作证，对一长串数字按照从低到高的顺序进行排序，与解决一个巨大的数独难题一样复杂，你可能会认为我已经失去了理智。你肯定会质疑为什么纳税人的钱被浪费在一个无聊主题的审判上。
然而，将案件告上法庭可能比第一印象所认为的更有价值。判定此类任务的相对难度这种基础性难题是数学和计算机科学中最致命的问题之一：P与NP问题，自1971年提出以来一直悬而未决。这个问题的解决对现实世界产生巨大影响，影响医学、人工智能、互联网安全和许多其他领域。由于这些原因，P与NP问题是克莱数学研究所选出的我们这个时代最重要的七大千禧年奖问题之一。
民事案件P与NP中的“P”代表“多项式时间”（Polynomial time）。当你增加输入的大小时，如果（理想版本的）计算机需要相应成比例更长一些的时间来完成其给定的任务，那么这个计算机程序就是以多项式时间运行。列表排序是P问题的一个完美示例，其中有已知且简单的方法对列表进行排序并验证列表是否正确排序，并且不会随着列表长度的增加而以某种荒谬的增长速度消耗时间。图释：对于可以在多项式时间内解决的问题（例

原文链接：裁决中的P与NP以及复杂性的复杂度

联系作者

文章来源：大数据文摘
作者微信：BigDataDigest
作者简介：普及数据思维，传播数据文化