計算復雜性理論起源于圖靈機模型的創(chuàng)立,并隨著P/NP問題的提出和大量P和NP問題的歸約在上世紀達到巔峰。 然而,基于最壞情況(worst case analysis)復雜度分析很快被發(fā)現(xiàn)未必能最好反應(yīng)實際情況。比如,在線性優(yōu)化(linear optimization)中久負盛名,時至今日仍是各大商用求解器baseline algorithm的單純形法(simplex method)很早被構(gòu)造出了存在具有指數(shù)時間復雜度的問題,而對線性優(yōu)化相對不那么實用的算法(橢圓法,后來的內(nèi)點法)卻具有多項式時間。為此,學者們提出了所謂平均分析法(average case analysis),如今則有更多更加平滑的分析手段。比如前面線性優(yōu)化的指數(shù)時間例子中,反例是非常「病態(tài)」且不夠魯棒(一點點擾動就可以讓問題變得容易),這和現(xiàn)實世界大部分問題并不match。 計算復雜性分析也帶來了許多其它的問題。首先,一些學者會認為P!=NP猜想毫無意義,一些學者則會認為它們和黎曼猜想同等重要。這或許和一些對于非確定性圖靈機(nonderterministic Turing machine)的現(xiàn)實構(gòu)造出現(xiàn)曙光有關(guān)系(量子計算機)。不管如何,證明猜想都應(yīng)當很不容易。另外,計算復雜度的大O理論或許太模糊了:在現(xiàn)實當中,一個算法的運行速度是和整個多項式的系數(shù)構(gòu)成密切聯(lián)系的,O(N^2.9+10000N)的算法相比O(N^3+N)的算法具有更小的大O復雜度,但實際當中很可能會不如后者。而且,復雜度理論很難很好地結(jié)合計算機內(nèi)存使用等其它軟硬件相關(guān)但對算法運行也非常有影響的因素。最后,即使我們假定P!=NP,一個NP問題是否就一定是沒有希望的?事實上,隨著近十年商用求解器和整數(shù)規(guī)劃算法的(硬件)發(fā)展,對許多經(jīng)典的NP complete問題,我們已有許多非常成熟的算法,可以精確求解中等規(guī)模的算例(如果允許近似解,則就有更多更有效的算法)。我們應(yīng)當如何考察計算復雜度理論在如今實際計算中的現(xiàn)實意義呢?如果有正面的例子,歡迎舉出,反例當然也可以。 問題比較大,可以涉及的東西也比較多,以上是本人想到的一些點。歡迎來分享你的(正面或反面的)見解,謝謝。 對一線程序員來說,計算復雜性理論是極其實用的。說成“一刻都離不開的指路明燈”都不為過。 當然,如果你段位過低,連個鏈表都玩不轉(zhuǎn)、只會跟著大佬念口訣、瞇著眼睛裝大神玩油膩;或者段位過高,破解個MD5/AES/RSA玩一樣,那么它對你的確沒多大指導作用。 剛好前幾天寫了個相關(guān)回答,懶得另外寫了,就以它為例吧: 要設(shè)計一段C++程序?qū)⑦@組數(shù)按要求重新排序時,有哪些好的算法? 明顯可以看出,程序員設(shè)計諸如qsort等算法時,每一步都在復雜度理論的指導下——這個算法至少需要多高的復雜度?我現(xiàn)在這個實現(xiàn)有沒有達到最佳復雜度?如何證明? 事實上,如果你看過高德納的《計算機程序設(shè)計的藝術(shù)》這本書,那么一定對這位大佬每個算法必證“該算法是否已經(jīng)最優(yōu)”印象深刻。 很顯然,如果沒有復雜性理論,算法設(shè)計實踐就成了無頭蒼蠅;相反,在解決一件事之前就知道、甚至可以嚴格證明“我這樣是否已經(jīng)最優(yōu)”,這是高級程序員技術(shù)素養(yǎng)的體現(xiàn)。 如果沒有這個能力的話,那么或許很簡單的需求你都得幾百上千萬的往里面砸錢。 比如,我就遇到過可以用800行代碼秒殺二三十萬行的現(xiàn)實案例:計算機基礎(chǔ)知識對程序員來說有多重要?就在這個案例中,一竅不通卻好裝X的經(jīng)理們做了個設(shè)計,把O(N)復雜度的一個數(shù)據(jù)庫任務(wù)搞成了O(N^3),致使項目失敗。 當然,復雜性理論并非毫無缺憾。 這是一個從一開始就故意設(shè)計的非?!按植凇钡亩攘糠桨?。原因很簡單,程序以及被它控制的硬件系統(tǒng)過于復雜,是不可能精確計算的。 類似的,“喂”給算法的數(shù)據(jù)是多變的、實際執(zhí)行算法的機器有cache、cache有多種映射模式、CPU有架構(gòu)和指令集的差異、有串行和并行的區(qū)別,等等。 那么,想要在如此復雜的條件下找出最優(yōu)化實現(xiàn),僅靠復雜性理論顯然是不夠用的。 但是,請注意:平均分析法(average case analysis)等東西并不是算法復雜性理論的顛覆者,而是它的推廣和延申、是考慮了數(shù)據(jù)分布等額外維度的算法復雜性理論。 事實上,在一線程序員的實踐中,他們早就本能的應(yīng)用了類似的分析方法,甚至絕大多數(shù)情況下比學術(shù)界想的更多更細:比如考慮cache算法本身、比如考慮系統(tǒng)中大量不同程序不同子系統(tǒng)的總吞吐量平均利用率、比如硬件的利用和加速,等等。 甚至于,工業(yè)界還可以利用profile乃至實時profile,實際的觀察分析程序熱點、針對性的解決問題——以至于“不要過早優(yōu)化”很早就成了一句耳熟能詳?shù)母裱浴?/p> 當然,這事實上也證明了“復雜性理論”不太夠用、尚不足以精確指導太過復雜的實現(xiàn),這才不得不找profile要效率。 至于N是否等于NP這個問題嘛…… NP問題并不等于“無法解決的問題”,而是“隨著規(guī)模提升需要算力飛快增長、使得人們束手無策的問題”——所以解決小規(guī)模、中等規(guī)模的NP問題說明不了任何問題。因為它本來就很容易解決。 這里的根本矛盾在于,NP問題的“規(guī)模-算力需求”曲線提升太過陡峭、使得規(guī)模稍大時,集于我們現(xiàn)在認識水平的計算就動輒要求耗盡整個宇宙的資源并計算到宇宙終結(jié)之后。但與之同時,這些問題的驗證卻頗為容易,和解決它的難度恰成鮮明對比。 那么,驗證難度這么低的問題,是不是計算難度就一定要那么高呢? 或者說:證明P=NP實質(zhì)上是要求我們找到一種通用的解法、從而把那些數(shù)量稍微多一些就干掉宇宙但驗證起來并不困難的難題往回拉一拉,拉到可接受的范圍內(nèi)(也就是多項式復雜度)。 相對應(yīng)的,P!=NP則要求我們證明這種解法不存在,O(N!)就是O(N!),哪怕答案可以在多項式范圍內(nèi)驗證,這個問題也不可能在多項式范圍內(nèi)解決。 這個問題當然是非?,F(xiàn)實也非常緊迫的。它關(guān)系到很多很多方面,從網(wǎng)上支付的安全性到復雜系統(tǒng)的仿真優(yōu)化。它看起來簡單清晰,驗證容易并不等于算起來就容易嘛;但想要證明或者推翻它,難度卻大的可怕——雖然很多加密算法就是集于P!=NP這個“一看就正確”的假設(shè);但假設(shè)畢竟只是假設(shè),一旦推翻,后果嚴重。 總之,這東西乍看起來和“任意一個大偶數(shù)都可以表示為兩個素數(shù)的和”的哥德巴赫猜想一樣,只是一種“思維游戲”;但和我們生活的關(guān)聯(lián)并不?。夯蛟S證實P!=NP并無太大影響,可一旦推翻…… |
|