計算機科學家說的“難題”是真正的難題,老百姓說的難題

當一個計算機科學家說“難題”的時候,他說

的可是真正的難題。

老百姓說的難題,通常都不是真的難題。比

如你讓一個小學生做一道高中數學題,他會

說這是一道難題

旦這個難度是相對而

言的,換個數學家來,高中數學題根本不叫

事兒。老百姓愛說“難者不會會者不難”,其

實具有這個性質的事兒都不是真的難題

真正的難題,得是絕對意義上的難。哪怕有

道題,現在活著的所有人都不會做,你也

很難說將來會不會有人找到一個巧妙地解

法,他一說那個解法大家都會覺得很簡單

所以那還不能算“絕對意義上的難

而計算機科學家,找到了一種絕對意義上的

難題。術語叫“NP困難(NP-hard)”。如

果再強行翻譯一下,大約叫“非確定性多項

式困難”不過你不必在意這個術語,你

只需知道,凡是“NP困難”的問題,都是絕

對的難題就行

為了理解這一點,咱們先看看什么是簡單的

問題

比如現在給你一份學生名單,讓你找一找,

其中有沒有一個叫“王小二”的學生,這就是

個簡單問題。簡單體現在計算時間短。你

只需要把名單上的名字過一遍就行。對計算

機來說,這是最簡單的搜索。我們容易理

解,如果名單上有N個名字,那么搜索時

間將會和N成正比。

好,再看第二個問題。還是N個學生,現

在讓你按照考試分數給他們排個名次。如果

你手動,先挑最高分,再挑第二高的分這么

排,你就太慢了。如果你對計算機算法有

定了解,你大概知道有一些特別聰明的排序

算法。其中最快的排序算法所需要的運行l

間,大約和Nog(N)成正比。排序比搜索

要慢一些,但是這個時間也還可以,我們仍

然可以說這是一個簡單問題。

什么叫“困難問題”呢?請看第三題

在一張地圖上有N個城市,想象你是一

推銷員,你能不能找到一條最短的路線,不

重不漏地經過所有這些城市去做推銷,然后

回到起點。比如像下面這條路線

這個問題聽起來很直觀,好像挺簡單,這不

就是快遞員每天都面對的問題嗎?但是,這

是一個非常難的問題。上面圖中就是一條看

起來不錯的路線,但是你怎么知道它是不是

有可能路線中*最短的*一條呢

這個問題叫做“旅行推銷員問題( Traveling

Salesman Problem)”。這是一個最著名的

組合優化問題。這是一個“NP困難”問題。

解決這個問颎沒有什么特別聰明的計算機算

法

你幾乎就是只能把這些城市的所有

排列組合都計算一遍,看看其中哪個最短。

你所需要的計算時間,不是跟N成正比

如果是10個城市,你得嘗試超過36萬種

路線。如果是15個城市,你得嘗試超過

871億種路線![1

這才叫難題。難題的意思,就是換誰來也沒

用,根本就沒有巧妙解法,只能老老實實地

這么算,而計算它所要消耗的時間是你無法

忍受的

1970年代,計算機科學家發展了一套“計算

復雜性”理論,“NP困難”這個概念就是那時

候提出來的。1972年,加州大學伯克利分

校的理查德·卡普( Richard Karp)證明旅

行推銷員問題是個NP困難問題。這也就是

說,不但現在沒有好的解法,而且我們在理

論上證明,這個問題它就幾乎不可能存在什

么好的解法

我為什么要說“幾乎”呢?因為這里面涉

及到一個數學猜想,叫“P=NP”,也就是說

也許還有存在簡單算法的一線希望,不過多

數計算機科學家不相信那個猜想.這件事

無關本文主題。

總而言之,“NP困難”是真正的困難。連計

算機都認為它是個難題。那我們應該怎樣面

對這樣的難題呢?這取決于你是個實用者,

改進者,還是競爭者。