裁決中的P與NP以及復雜性的復雜度

AIGC動態歡迎閱讀

原標題：裁決中的P與NP以及復雜性的復雜度
關鍵字：問題,復雜度,函數,數學,電路
文章來源：大數據文摘
內容字數：0字

內容摘要：

作者：Benjamin Skuse
譯者：zzllrr小樂
如果我請你出庭作證，對一長串數字按照從低到高的順序進行排序，與解決一個巨大的數獨難題一樣復雜，你可能會認為我已經失去了理智。你肯定會質疑為什么納稅人的錢被浪費在一個無聊主題的審判上。
然而，將案件告上法庭可能比第一印象所認為的更有價值。判定此類任務的相對難度這種基礎性難題是數學和計算機科學中最致命的問題之一：P與NP問題，自1971年提出以來一直懸而未決。這個問題的解決對現實世界產生巨大影響，影響醫學、人工智能、互聯網安全和許多其他領域。由于這些原因，P與NP問題是克萊數學研究所選出的我們這個時代最重要的七大千禧年獎問題之一。
民事案件P與NP中的“P”代表“多項式時間”（Polynomial time）。當你增加輸入的大小時，如果（理想版本的）計算機需要相應成比例更長一些的時間來完成其給定的任務，那么這個計算機程序就是以多項式時間運行。列表排序是P問題的一個完美示例，其中有已知且簡單的方法對列表進行排序并驗證列表是否正確排序，并且不會隨著列表長度的增加而以某種荒謬的增長速度消耗時間。圖釋：對于可以在多項式時間內解決的問題（例

原文鏈接：裁決中的P與NP以及復雜性的復雜度

聯系作者

文章來源：大數據文摘
作者微信：BigDataDigest
作者簡介：普及數據思維，傳播數據文化