AIGC動態(tài)歡迎閱讀

原標(biāo)題：裁決中的P與NP以及復(fù)雜性的復(fù)雜度
關(guān)鍵字：問題,復(fù)雜度,函數(shù),數(shù)學(xué),電路
文章來源：大數(shù)據(jù)文摘
內(nèi)容字?jǐn)?shù)：0字

內(nèi)容摘要：

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

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

聯(lián)系作者

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