看經典美劇探索數學世界——海森堡不確定原理與P/NP複雜度問題

2020-12-07 遇見數學

《數字追兇》102劇情簡介

在這集中發生了一系列的搶劫銀行犯罪事件，但並沒有出現任何暴力行為。查理推理出下一起搶劫案發生的地點之後，FBI設下了埋伏。不料被暗中隱藏的槍手大開殺戒。槍林彈雨中，一位特工中槍倒地。FBI的幹預改變了搶劫犯們的行為，並且揭開了一段更加撲朔迷離的劇情……

什麼是海森堡不確定原理?

查理告訴唐，海森堡測不準原理認為在一個系統中，測量數據的行為會影響系統本身的數據。但查理過後也承認了，這不是原理本身描述的性質。

圖自網絡

事實上查理的敘述並不那麼嚴謹：假設有一粒漂浮在空氣中的塵埃，而我們想要非常精確地測量出它的位置。此時我們一定會使得空氣發生流動，從而使這粒塵埃分子移動。這是物理學家們習以為常的事實了。

海森堡測不準原理真正想要表述的應該是，我們不能同時完美地測量出任何東西的精確位置與精確速度，尤其是當被測量物為一粒電子時。這個誤差的結果跟普朗克常量差不多，即10-34 焦耳每秒。焦耳每秒是一個描述宏觀量的單位（宏觀量，比如千克和米） 所以說在宏觀的體系中，這點誤差小到完全可以忽略。我們測量的東西越小，這個法則就越重要。

這個原理，從它的根基上而言，跟物理完全沒有任何關係。事實上，它的基本形式解釋了一個函數和它的傅立葉變換形式的關係。我們得出結論，傅立葉變換是量子力學的基礎，所以傅立葉變換自然在物理學中也是有意義的。美國數學協會有一篇很精彩的文章[1]，這篇文章正是從這個角度，解釋了傅立葉變換。

[1] ams.org/publicoutreach/feature-column/fcarc-uncertainty

什麼是 P vs NP 問題？

圖自網絡

P/NP問題是一個邏輯學的問題（或計算機理論科學）。假設我們有一個問題，希望用計算機來解決。比如說，我們想要用計算機找出旅行商問題的答案。假設一位商人需要走過全世界的五十個城市。 已知的條件是每個城市的航班的價格，而商人想要花在路上的錢儘可能少。顯然我們可以找出「僅僅」 50×49×48×....3×2×1 種可能的方案。沒有人會想要手算每一條線路的總價格，所以我們編程，讓計算機來幫我們解決這個問題。但計算機會花多少時間來解決這個問題呢？ 這個問題從以下的方式被構想出來：假設我們在這個問題中有 n 個地點。有沒有一個算法僅僅需要O(f(n)) 步呢？在這裡，我們把大寫的 O 定義為算法的漸進時間複雜度。其中 n 是問題的規模，在一個指定的數學模型中，規模往往可以由人為設定並輸出此規模的結果。在代碼中，n 可以理解為 input 的一個值。因此 n 可以看做是一個未知數。f(n) 可以簡單理解為代碼循環了 n 次。那麼 O 的含義就好理解了，O 其實是一個關於f(n)的函數，有固定的推導算法，其定義了算法所需的時間與 n 的增長的關係，稱為算法的漸進時間複雜度，簡稱時間複雜度。一般來說，如果有一個算法能夠使問題在O(f(n))步以內解決，那麼我們稱這個問題屬於 f 級別複雜度類別。

P級別複雜度類別問題，是一個由一系列 YES/NO 問題組成的問題，並且這個問題能夠在多項式時間內被解決。也就是說，P 級別複雜性類問題是說，這個問題存在著一個算法使得 O(f(n)) 小於多項式 f(n)。我們也說 P 是一些能夠由多項式時間以內的算法來找出答案的問題。NP複雜性類是一些更複雜的問題。那NP和P問題有什麼區別呢？有些問題計算起來很容易，利用多項式算法很快能解決，比如求若干個數的乘積，這類問題被稱作 P 問題；另一類問題計算過程比較繁瑣，但驗證答案卻很容易，比如把整數 44427 進行因數分解，求解過程可能會很費時，但如果告訴你答案是177×251，簡單計算即可驗證答案是對的，這類問題就被歸為NP問題。也就是說如果一個驗證問題答案的算法可以在多項式時間以內完成，那麼是不是存在一個相應的算法，對於此問題，能夠在多項式時間內找到答案？ 這乍一聽好像有點蠢，尋找答案與驗證答案對於計算機來說幾乎是同一件事，但是這是目前世界上公開的數學問題中，最棘手的一個。 P對NP問題是克雷數學研究所高額懸賞的七個千禧年難題之一，只要給出正確或否定的論文並成功論證P與NP是否能夠相互轉化，$1,000,000的賞金就是你的囊中之物。

細心的觀眾注意到查理說掃雷是一個NP問題。查理的描述其實不那麼清晰，因為他沒怎麼講清楚如何解決 P vs NP 問題。 NPC 問題是 NP 問題的一個小小的子集，NPC 問題有可能不是 P 問題。本質上來說，NPC問題是最難的NP問題。理察·凱伊用數學人工智慧證明了掃雷遊戲是一個NPC問題。人們可以通過訪問他的網站[2]獲得更多有關掃雷的數學問題的信息。旅行商問題也是NPC問題。

[2] web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

統計家眼中的死亡

查理對唐說，從統計學角度上看，他已經死了。唐槍口逃生，撿回了一條命，查理認為，這種好運不會再有第二次了。查理這麼說可能是正確的，一個人在槍口脫險後，他會比普通人更加容易喪命於槍口之下。 畢竟，那些經歷過槍戰的人更有可能參與到下一場槍戰中，因為這幫人包括警察，軍人，僱傭軍和幫派等。查理的推斷正確嗎？特別地，他的哥哥是否更有可能是因為在參加的槍戰中負的傷而死亡的呢？（完）

參考：pi.math.cornell.edu/~numb3rs/luthy/num104.html譯者+校對：毛線團君

相關焦點

  • 什麼是 P = NP 問題?
    看到這裡我們get了一個非常重要的概念(敲黑板劃重點)：P類問題是可以在多項式時間內解決並驗證的一類問題，NP類問題是可以多項式時間驗證但是不確定能否在多項式時間內解決的一類問題。等等！這個世界並不是只有多項式時間這麼簡單，我們還知道有指數函數形如2^n這個計算量已經非常可怕，更不要說n^n和n!這種問題了。對於計算機而言，它不知道問題難不難，對它而言就是拆解成非常多的步驟去執行，去衡量計算機認為難或者不難或許可以從其執行時間來看，在排除代碼實現差異來說，執行時間越長的問題通常都會比較難。
  • 科學網—中科大實驗驗證新形式海森堡不確定原理
    本報訊（記者楊保國） 近日，中國科學院院士、中國科技大學教授郭光燦領導的中科院量子信息重點實驗室李傳鋒研究組，在實驗上突破了量子力學中「經典
  • 中國科大實驗驗證新形式的海森堡不確定原理
    近日，中國科學技術大學郭光燦院士領導的中科院量子信息重點實驗室實驗驗證了新形式的海森堡不確定關係。李傳鋒博士研究組完成的實驗表明，在待測粒子的「量子信息」事先被存儲的情況下，「經典」的不確定關係能夠被違背。
  • 海森堡「測不準」原理-最精密的數學推導出的唯心主義
    一個電子的動量，只有當你測量時，才有意義。假如這不好理解，想像有人在紙上畫了兩橫夾一豎，問你這是什麼字。嗯，這是一個「工」字，但也可能是橫過來的「H」，在他沒告訴你怎麼看之前，這個問題是沒有定論的。現在，你被告知：「這個圖案的看法應該是橫過來看。」這下我們明確了：這是一個大寫字母H。只有觀測手段明確之後，答案才有意義。
  • 【量子物理】海森堡不確定性原理經典解釋被實驗推翻!
    為了拍攝照片，科學家可能要向電子的表面發射一顆光子。這會暴露電子的位置，但光子也會把能量傳遞給電子，使它發生位移。探測電子的位置會不確定地改變它的速率，而測量行為引發的不確定性足以讓這個原理成立。和學生們所學的相反，旁觀者並不總能感覺到量子不確定性。一項新實驗證實，對一個量子系統的測量不一定會導致不確定性。研究推翻了大量關於量子世界為何如此不可知的解釋，但可探測的最小尺度的基本極限仍然不變。
  • 海森堡測不準原理,指的是用光測不準粒子,但並非指其他方法都測不準,是這樣嗎?
    (宇宙探索QQ群：1145693748）海森堡測不準原理
  • [洛穀日報第58期]初賽備考乾貨:P、NP、NP-hard、NPC問題
    NP問題不是非P問題上面那種NP問題的定義會變得非常爆炸，因為你有時候並不能證明這個問題是不是一定沒有多項式解，也就是說不確定現在這個不存在多項式複雜度的問題在未來也不存在多項式複雜度解法，顯然這些問題你既不能歸入P又不能歸入NP，所以你還要再定義一個別的東西來表示他們，反正這個定義GG了回顧之前所說，我們一開始的希望是找到多項式複雜度的解法，接著才會去考慮劃分這些問題
  • 數字追兇:不確定原理/NP問題/統計學上的死亡
    沒有人會想要手算每一條線路的總價格，所以我們編程，讓計算機來幫我們解決這個問題。但計算機會花多少時間來解決這個問題呢？ 這個問題從以下的方式被構想出來：假設我們在這個問題中有 n 個地點。有沒有一個算法僅僅需要O(f(n)) 步呢？在這裡，我們把大寫的 O 定義為算法的漸進時間複雜度。其中 n 是問題的規模，在一個指定的數學模型中，規模往往可以由人為設定並輸出此規模的結果。
  • 關於不確定性原理,海森堡錯了嗎?
    在量子力學中，「不確定性」是一個高頻出現的詞彙。有觀點認為，不確定性的意思是這個世界具有某種我們無法確定的東西。但多數物理學家認為，不確定性是自然本身的一種固有性質。固有的不確定性是現代量子力學的創始人之一海森堡的一個核心思想。他提出的不確定性原理表明，我們不可能同時知道一個粒子的所有性質。
  • 玻爾巧遇海森堡,量子迷霧一掃光,普朗克常數再發威
    玻爾被難住了，尷尬地下不來臺，但是玻爾畢竟是玻爾，一個非常有經驗的演講者，他回答說：「這是一個好問題，年輕人。」如今玻爾的這個回答，已經成為很多教授迴避尖銳問題的必殺技。我們現在回頭看玻爾的原子模型。四、h普朗克常數——量子力學的大門就在物理學家們都在一籌莫展的時候，海森堡發現了量子世界的一個公式[x,p]=xp-px=ih/2π，這個公式稱為基本對易關係。根據量子力學原理，可以推導出不確定關係ΔxΔp≥h/4π。
  • 海森堡的測不準原理
    雖然海森堡因必考的實驗問題表現不佳而差一點無法通過口試，但他還是於 1923 年獲得了博士學位，論文討論的是流體力學上的一個問題。在得到博士學位後，他到哥廷根做玻恩（Max Born，1954年諾貝爾物理獎得主）的助理，之後又到哥本哈根玻爾（Niels Bohr，1922 年獲得諾貝爾獎）所主持的研究所跟隨他一起做了一年研究。
  • 海森堡:一個在不確定的世界裡深情活著的人
    經過了一段時間的探索和研究1921年，他在《物理學雜誌》上發表了論文，研究層面便有了新的突破。在海森堡獲得博士學位之後，應尼爾斯·玻爾的邀請，前往哥本哈根擔任他的助手，這也便成為了研究工作生涯的「高光時刻」。1927年3月，海森堡再次給《物理學雜誌》投稿，以論文的形式闡釋了他在物理學領域的最高貢獻：不確定性原理。
  • 「海森堡原理」依然挑戰科學認識的極限
    在大約90年之前，維爾納·海森堡提出了量子世界遵循的「不確定性原理」，在原理發表後的大約90年，三個國家的研究人員組成了一支合作團隊，他們對量子物理學的「海森堡原理」提出了新的見解，第一次用嚴格的數學公式描述海森堡的「不確定性原理」，他們的研究成果取得了實際性的進展，加深了人們對這一原理的理解
  • 原來宇宙是不確定的?
    法國的數學家、天文學家、法國科學院院士，同時也是拿破崙的老師，拉普拉斯，曾經用牛頓方程計算出了行星軌道，並把結果展示給拿破崙看。拿破崙問到：在你的理論中，上帝在哪兒呢？拉普拉斯平靜的回答：陛下，我的理論不需要上帝這個假設。
  • 我國科學家確定自旋玻璃三維伊辛模型的計算複雜度下限研究
    中國網/中國發展門戶網訊 日前，中國科學院金屬研究所研究員張志東確定了自旋玻璃三維伊辛模型的計算複雜度的下限，為一個絕對極小核模型的計算複雜度，它包含一個與其最近鄰平面相互作用的自旋玻璃二維伊辛模型，是亞指數時間，超多項式時間
  • 解決計算機數學中最著名的難題P=NP將徹底改變人類文明進程
    從早期農業到太空探索，解決數學問題似乎是人類生存的一個關鍵因素。自上世紀70年代以來，一些曾經單調乏味的計算問題在一瞬間就可以解決，這主要是由於計算能力的指數級增長。然而，一些獨特的問題僅僅通過技術進步是無法解決的，即使對於最強大的計算機來說，解決這些問題所花費的時間比人的一生還要長。
  • 世界從不確定走入確定,又從確定邁入不確定,上帝擲不擲骰子?
    在科學誕生之前，世界對於人類而言完全是不確定的。人類不知道何時會發生火山地震，人類不知道雨雪為什麼會降臨於世，人類也不知道旱澇災害為何會交替出現，更不明白旱災為什麼總是與蝗災相伴。而對於太陽和月亮的交替出現，人類更是一頭霧水，可以說，這個世界上所發生的一切自然現象，人類就那樣看著，人類對這一切無比熟悉卻又是一無所知。
  • 【量子物理】現代科學家對「不確定原理」的解釋.
    隨著量子理論的逐漸成熟，這個類比已經被人們所淡忘，然而在過去的十年裡關於它的討論又再一次興起。雖然最近多個實驗表明這個類比是有缺陷的，但是一個由英國、芬蘭和德國物理學家組成的研究小組認為，這些實驗都沒有嚴格遵守海森堡的原始表述。海森堡不確定性原理可以表述為，對於一個微觀粒子，我們不可能同時精確地測量出其位置和動量。我們測得其中一個值越精確，那麼另一個值就會變得越粗略。
  • 量子力學那點事群雄逐鹿之二:不相容與不確定
    首先，泡利不相容原理是量子論的巔峰，可以用來解釋玻爾—索末菲模型，還發展了量子論，不僅可以用在氫原子模型，還可以用在多原子上。其次，泡利不相容原理還可以由量子力學推導出來，可是這個工作並不是泡利完成的，不相容原理可以推導出電子自旋，又很可惜泡利錯過了，依據不相容原理，費米解決了費米—狄拉克統計。
  • 海森堡不確定性原理,科學界最重要的創見之一,量子力學的基石!
    到了20世紀20年代中期，歐洲的幾位物理學家狂熱地追求一個能夠更加完善而一致地描述亞原子世界的數學理論。彼時的玻爾已經回到了哥本哈根，他也是追求數學理論的狂熱者之一。1925年的夏天，從一次花粉症發作中恢復過來的海森堡在一個名為黑爾戈蘭島的德國小島上養病，其間，他在構建用來描述原子世界的數學體系時取得了重大進展。但這是一種非常奇怪的數學表達，而這個表達所描述的原子行為更加離奇。