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

文章预览

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