[爆卦] 困擾計算機界多年的敏感度猜想被華人數已刪文

看板Gossiping作者 (asdf)時間4年前 (2019/07/30 18:05), 4年前編輯推噓307(334推 27噓 62→)
留言423則, 388人參與, 4年前最新討論串1/1
1992年，耶路撒冷希伯來大學的Noam Nisan和羅格斯大學的Mario Szegedy提出布林函數 敏感度猜想。這成為了計算機科學近三十年來最重要的開放性問題之一。這個月，Emor y大學的華人教授黃皓用兩頁紙證明了此問題。 證明在連結p3,p4 http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf 電腦科學家發明了各種衡量布林函數複雜度的方法。布林函數的敏感度就是將某輸入位 元反轉後使得輸出被反轉的機會。而“查詢複雜度”則是你需要確定多少個輸入位元才 能定下輸出位元。 每一種測度都以獨特的視角審視布林函數的結構。電腦科學家們發現幾乎所有測度都在 統一框架內互相相關，知道其中一個測量值讓你可以估計其它測量值。而這其中唯一的 格格不入者正是敏感度。 想像你在向銀行申請貸款，需要填一系列答案為是或否的問題。填完後銀行人員會告訴 你是否批准貸款。這個過程就是一個布林函數，你的答案是輸入位元，而銀行人員的決 定是輸出位元。 如果你的申請被拒，你也許會想在某個問題上撒謊來改變結果，例如年薪是否為5萬以上 ，如果改變這個回答就能徹底反轉最後的決定，電腦科學家稱該布林函數對於這個特定 位元“敏感”。如果有7個問題的答案任一改一下都能改變結果，此布林函數的敏感度為 7。 電腦科學家把布林函數的敏感度定義為在所有可能的申請中最大的那個敏感度值。換句 話說，這個測度計算在最極端的情況下，有多少道問題是真正至關重要的？而最多需要 幾個問題可以做出決定就是布林函數的查詢複雜度。 除了敏感度以外，電腦科學家已經證明了所有測度值之間都成多項式關係。例如，一個 測度值可能大約是另一個測度值的平方，或立方，或平方根。只有敏感度尚未融入到這 個優美的框架之中。 黃皓在2012年從數學家Michael Saks聽到了這個猜想。他立刻被這個猜想的簡潔優美吸 引了。“自那一刻起，我不斷固執地思索著這個問題。” 黃皓知道如果數學家能證明某個關於不同維度下方形頂點集合的簡潔猜想，那麼敏感度 猜想就等於被證明了。n個輸入位元0或1和n維方形頂點有一種自然的映射關係，它可以 被視為該頂點的座標。 如下圖，2位元串共有4種情況00, 01, 10和11，對應於二維平面上正方形的頂點(0,0), (0,1), (1,0)和(1,1)。同樣，8個3位元串對應于三維立方的8個頂點，更高維下也以此 類推。布林函數等於把所有頂點塗上兩種不同顏色的方法（例如輸出為1塗藍色，0塗紅 色）。 https://m.imgur.com/CyoAoLS?r 2013年，黃皓認為證明的最佳思路為將網路轉化為一個代表兩點是否相連的矩陣，並探 索這個矩陣的特徵值。在接下來的5年裡，他不斷重溫這個思路，但一直沒有突破。“至 少思考這個問題經常讓我很快入眠。” 2018年，黃皓突然意識到可以借用柯西交錯定理。這個定理將矩陣的特徵值和其子矩陣 的特徵值掛勾，這意味著用該定理來研究方形和其頂點子集再恰當不過了。 黃皓決定向國家科學基金申請經費，當他坐在馬德里的酒店裡寫申請書時，突發意識到 只要把矩陣裡某些數的符號逆轉就能把問題完全解決。這麼一來，他能證明n維方形中任 一超過一半頂點的集合中，必有一點和至少n個其它同在該集合中的點相連。敏感度猜想 終於被證明。 當同行評審Mathieu收到黃皓的論文時，她已經做好完全看不懂的準備。但是證明非常簡 潔，Mathieu和其他同行一讀完就理解了。她說：“我覺得今年秋天所有組合數學碩士課 程都可以教這個定理了，而且一節課就可以教完。” 黃皓簡介: 出生於汕頭，2003年憑藉優異的成績被保送至北京大學攻讀數學。黃皓在北 京大學舉辦數學建模與計算機應用競賽中獲得三等獎，並出現在北大數學百年學生名錄 上。2007年畢業後，黃皓在美國加州大學洛杉磯分校讀博，師從著名數學家Benny Suda kov教授，並於2012年獲得學位。現擔任Emory大學數學系助理教授。主要研究領域包括 極值組合、圖論及計算機理論。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.90.146 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1564481101.A.763.html
推
07/30 18:05, 4年前 , 1F
摁摁
07/30 18:05, 1F
→
07/30 18:05, 4年前 , 2F
跟我
07/30 18:05, 2F
→
07/30 18:05, 4年前 , 3F
3樓帥
07/30 18:05, 3F
推
07/30 18:05, 4年前 , 4F
想的
07/30 18:05, 4F
→
07/30 18:05, 4年前 , 5F
工啥
07/30 18:05, 5F
推
07/30 18:05, 4年前 , 6F
嗯嗯 好 跟我想的一樣
07/30 18:05, 6F
→
07/30 18:06, 4年前 , 7F
中國人不可信
07/30 18:06, 7F
推
07/30 18:06, 4年前 , 8F
簡單，想一下就知道了
07/30 18:06, 8F
推
07/30 18:06, 4年前 , 9F
跟我想得一樣 可惜我的紙只有一頁能寫
07/30 18:06, 9F
推
07/30 18:07, 4年前 , 10F
我還是等李永樂老師吧
07/30 18:07, 10F
→
07/30 18:07, 4年前 , 11F
原來要兩頁才能證明出來 難怪我沒辦到
07/30 18:07, 11F
推
07/30 18:07, 4年前 , 12F
厲害
07/30 18:07, 12F
推
07/30 18:07, 4年前 , 13F
中國人一定4造假
07/30 18:07, 13F
→
07/30 18:08, 4年前 , 14F
我不信我不信
07/30 18:08, 14F
推
07/30 18:08, 4年前 , 15F
這個可以跟貝葉斯合體
07/30 18:08, 15F
推
07/30 18:08, 4年前 , 16F
哦哦我一看他的論文就想通了
07/30 18:08, 16F
→
07/30 18:09, 4年前 , 17F
當初怎麼沒想到
07/30 18:09, 17F
推
07/30 18:09, 4年前 , 18F
嗯嗯 跟我想的一樣
07/30 18:09, 18F
推
07/30 18:09, 4年前 , 19F
略懂
07/30 18:09, 19F
推
07/30 18:09, 4年前 , 20F
人家也要當美國人了啦
07/30 18:09, 20F
推
07/30 18:10, 4年前 , 21F
難道是哥布林殺手幹的
07/30 18:10, 21F
推
07/30 18:10, 4年前 , 22F
好厲害
07/30 18:10, 22F
→
07/30 18:10, 4年前 , 23F
文組看不懂辣幹
07/30 18:10, 23F
噓
07/30 18:11, 4年前 , 24F
我早就想出來了 沒時間發表論文
07/30 18:11, 24F
推
07/30 18:11, 4年前 , 25F
哥布林很敏感嗎？
07/30 18:11, 25F
推
07/30 18:11, 4年前 , 26F
啥米代誌
07/30 18:11, 26F
推
07/30 18:11, 4年前 , 27F
跟我想的差不多
07/30 18:11, 27F
推
07/30 18:12, 4年前 , 28F
碩士課程就可以教，一定有什麼盲點
07/30 18:12, 28F
推
07/30 18:12, 4年前 , 29F
明明就6頁PDF
07/30 18:12, 29F
→
07/30 18:12, 4年前 , 30F
跟我想的差不多
07/30 18:12, 30F
→
07/30 18:12, 4年前 , 31F
工三小
07/30 18:12, 31F
推
07/30 18:13, 4年前 , 32F
居然是用矩陣特徵值證明 真的想不到...
07/30 18:13, 32F
推
07/30 18:13, 4年前 , 33F
嗯嗯跟我想的差不多
07/30 18:13, 33F
→
07/30 18:13, 4年前 , 34F
布琳是正妹ㄇ 敏感度嘻嘻嘻
07/30 18:13, 34F
推
07/30 18:13, 4年前 , 35F
恩恩 我早就說是這樣
07/30 18:13, 35F
噓
07/30 18:13, 4年前 , 36F
false, not true
07/30 18:13, 36F
推
07/30 18:13, 4年前 , 37F
07/30 18:13, 37F
推
07/30 18:13, 4年前 , 38F
噢 原來是這樣啊
07/30 18:13, 38F
推
07/30 18:14, 4年前 , 39F
恩恩 跟我想的一樣
07/30 18:14, 39F
還有 345 則推文
還有 1 段內文
推
07/31 00:49, 4年前 , 385F
我以前讀計概的時候就把這證明寫在書本
07/31 00:49, 385F
→
07/31 00:49, 4年前 , 386F
的角落
07/31 00:49, 386F
推
07/31 00:52, 4年前 , 387F
嗯嗯(眼光飄移~
07/31 00:52, 387F
推
07/31 01:01, 4年前 , 388F
想吃汕頭火鍋
07/31 01:01, 388F
推
07/31 01:06, 4年前 , 389F
計概哪有在算數學，都best effort
07/31 01:06, 389F
推
07/31 01:13, 4年前 , 390F
推好證明
07/31 01:13, 390F
→
07/31 01:14, 4年前 , 391F
九頭蛇...
07/31 01:14, 391F
推
07/31 01:22, 4年前 , 392F
嗯很好 跟我想得一樣
07/31 01:22, 392F
推
07/31 01:23, 4年前 , 393F
超強
07/31 01:23, 393F
推
07/31 01:31, 4年前 , 394F
嗯 同感
07/31 01:31, 394F
推
07/31 01:56, 4年前 , 395F
恩恩我想也是
07/31 01:56, 395F
推
07/31 02:04, 4年前 , 396F
這證明真的很神，我們系做理論的教授證
07/31 02:04, 396F
→
07/31 02:04, 4年前 , 397F
明出來當天都超high XD
07/31 02:04, 397F
推
07/31 02:05, 4年前 , 398F
昨天也在想這個問題
07/31 02:05, 398F
推
07/31 02:51, 4年前 , 399F
差不多是這樣
07/31 02:51, 399F
推
07/31 03:06, 4年前 , 400F
Rose are red....
07/31 03:06, 400F
推
07/31 03:12, 4年前 , 401F
恩我也是這樣覺得
07/31 03:12, 401F
推
07/31 03:39, 4年前 , 402F
我才寫一頁半就有人先 寫完2頁發表，省
07/31 03:39, 402F
→
07/31 03:39, 4年前 , 403F
下我的力氣
07/31 03:39, 403F
推
07/31 03:56, 4年前 , 404F
這我真的看懂
07/31 03:56, 404F
推
07/31 05:44, 4年前 , 405F
本版廢文大賽火熱進行中ㄎㄎ
07/31 05:44, 405F
推
07/31 07:23, 4年前 , 406F
攻殺小
07/31 07:23, 406F
推
07/31 07:44, 4年前 , 407F
喔是
07/31 07:44, 407F
推
07/31 08:16, 4年前 , 408F
嗯嗯 都中文 我看得懂
07/31 08:16, 408F
推
07/31 08:40, 4年前 , 409F
快推，不然會被笑文組
07/31 08:40, 409F
推
07/31 09:00, 4年前 , 410F
終於可以升副教授了
07/31 09:00, 410F
推
07/31 09:19, 4年前 , 411F
嗯嗯
07/31 09:19, 411F
推
07/31 09:30, 4年前 , 412F
原來還沒被證明啊 我以為大家都知道
07/31 09:30, 412F
→
07/31 09:30, 4年前 , 413F
了
07/31 09:30, 413F
噓
07/31 09:32, 4年前 , 414F
哥布林的敏感度干我屁事
07/31 09:32, 414F
推
07/31 10:20, 4年前 , 415F
一堆中文字湊在一起,結果整篇看不懂
07/31 10:20, 415F
→
07/31 10:21, 4年前 , 416F
我當市長時，早就三次想過這答案了
07/31 10:21, 416F
→
07/31 10:26, 4年前 , 417F
看到寫華人就知道是強國人了
07/31 10:26, 417F
推
07/31 10:42, 4年前 , 418F
嗯嗯 跟我想的一樣
07/31 10:42, 418F
推
07/31 10:51, 4年前 , 419F
雖然看不懂，但這覺的這兩頁很屌XDD
07/31 10:51, 419F
推
07/31 10:52, 4年前 , 420F
笨
07/31 10:52, 420F
→
07/31 11:01, 4年前 , 421F
支那人就支那人 不敢寫 覺得羞恥嗎？
07/31 11:01, 421F
※ 編輯: bulls0722 (42.72.69.32 臺灣), 07/31/2019 12:10:38
推
07/31 12:24, 4年前 , 422F
恩恩,看完之後還是看不董
07/31 12:24, 422F
推
07/31 13:41, 4年前 , 423F
盜圖修個屁.......
07/31 13:41, 423F
‣ 更多 bulls0722 的文章
文章代碼(AID): #1TG1PDTZ (Gossiping)