什么是p問題、np問題和npc問題(已修改)
2025-01-25 23:28 本頁面
【正文】 什么是P問題、NP問題和NPC問題NP完全問題，是世界七大數(shù)學難題之一。NP的英文全稱是Nondeterministic Polynomial的問題，即多項式復雜程度的非確定性問題。簡單的寫法是NP=P?，問題就在這個問號上，到底是NP等于P，還是NP不等于P。數(shù)學上著名的NP問題，完整的叫法是NP完全問題，也即NP COMPLETE問題，簡單的寫法，是NP=P?的問題。問題就在這個問號上，到底是NP等于P，還是NP不等于P。證明其中之一，便可以拿百萬美元大獎。多流水線調(diào)度實際上是一個NP完全問題這個獎還沒有人拿到，也就是說，NP問題到底是Polynomial，還是NonPolynomial，尚無定論。NP里面的N，不是NonPolynomial的N，是NonDeterministic，P代表Polynomial倒是對的。NP就是Nondeterministic Polynomial的問題，也即是多項式復雜程度的非確定性問題。美國麻州的克雷(Clay)數(shù)學研究所于2000年5月24日在巴黎法蘭西學院宣布了一件被媒體炒得火熱的大事：對七個千僖年數(shù)學難題的每一個懸賞一百萬美元。以下是這七個難題。千僖難題之一：P(多項式算法)問題對NP(非多項式算法)問題千僖難題之二：霍奇(Hodge)猜想千僖難題之三：龐加萊(Poincare)猜想千僖難題之四：黎曼(Riemann)假設(shè)千僖難題之五：楊米爾斯(YangMills)存在性和質(zhì)量缺口千僖難題之六：納維葉斯托克斯(NavierStokes)方程的存在性與光滑性千僖難題之七：貝赫(Birch)和斯維訥通戴爾(SwinnertonDyer)猜想NP完全問題排在百萬美元大獎的首位，足見他的顯赫地位和無窮魅力。什么是P問題、NP問題和NPC問題。你會經(jīng)?？吹骄W(wǎng)上出現(xiàn)這怎么做，這不是NP問題嗎、這個只有搜了，這已經(jīng)被證明是NP問題了之類的話。你要知道，大多數(shù)人此時所說的NP問題其實都是指的NPC問題。他們沒有搞清楚NP問題和NPC問題的概念。NP問題并不是那種只有搜才行的問題，NPC問題才是。好，行了，基本上這個誤解已經(jīng)被澄清了。下面的內(nèi)容都是在講什么是P問題，什么是NP問題，什么是NPC問題，你如果不是很感興趣就可以不看了。接下來你可以看到，把NP問題當成是NPC問題是一個多大的錯誤。還是先用幾句話簡單說明一下時間復雜度。時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規(guī)模擴大后，程序需要的時間長度增長得有多快。也就是說，對于高速處理數(shù)據(jù)的計算機來說，處理某一個特定數(shù)據(jù)的效率不能衡量一個程序的好壞，而應該看當這個數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運行時間是否還是一樣，或者也跟著慢了數(shù)百倍，或者變慢了數(shù)萬倍。不管數(shù)據(jù)有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具有O(1)的時間復雜度，也稱常數(shù)級復雜度；數(shù)據(jù)規(guī)模變得有多大，花的時間也跟著變得有多長，這個程序的時間復雜度就是O(n)，比如找n個數(shù)中的最大值；而像冒泡排序、插入排序等，數(shù)據(jù)擴大2倍，時間變慢4倍的，屬于O(n^2)的復雜度。還有一些窮舉類的算法，所需時間長度成幾何階數(shù)上漲，這就是O(a^n)的指數(shù)級復雜度，甚至O(n！)的階乘級復雜度。不會存在O(2*n^2)的復雜度，因為前面的那個2是系數(shù)，根本不會影響到整個程序的時間增長。
試題試卷相關(guān)推薦
鄂ICP備17016276號-1