作者 jackliao1990 (j)標題 [爆卦] "P vs PSPACE問題"半世紀以來最大進展時間 Fri May 23 19:43:40 2025
https://arxiv.org/pdf/2502.17779
1960年代Juris Hartmanis與Richard Stearns首次提出嚴謹的時間與空間複雜度定義並創
建了複雜度類別P(可在多項式時間內解決的問題)與PSPACE(可在多項式空間內解決的問題)
所有演算法都依賴兩種基本資源：時間與記憶體空間
"是否所有PSPACE問題也都能在P中解決？"是資工核心問題
1975年Hopcroft、Paul和Leslie Valiant發明了第一個普遍模擬方法:可以用較少空間完成
原本需較多時間的任務(時間t可用O(t/logt)空間模擬)
科學家一度認為P≠PSPACE(任務需要的空間幾乎跟所需時間成正比，沒有更好的選擇)
然而後來研究證明:若兩資料不能同時佔用記憶體空間則進一步空間壓縮模擬是不可能的
之後的半世紀裡 "P VS PSPACE問題"研究陷入了瓶頸
直到麻省理工的Ryan Williams出馬
Williams來自阿拉巴馬農村，小時候用紙寫程式。高中就讀阿拉巴馬數理中學，後來進入
康乃爾大學學習。
他一度在課堂上被評沒天賦並被勸改行，但他仍獲得複雜度理論先驅兼圖靈獎得主Juris
Hartmanis的賞識與指導
儘管他申請博班被拒絕
他仍繼續思考P VS PSPACE問題
Williams用Cook和Mertz的極省空間樹狀運算演算法將原始圖形化時間流程轉換為樹狀結構
節點代表模擬一段時間的tape狀態變化，節點僅用少量空間遞迴呼叫，記憶體可重複使用
最終發現:1.任一時間t(n)>=n的計算都能用O(√tlogt)空間模擬完成
2.有些問題可在O(n)空間內解但永遠無法在n2-ε時間內解決，證明時間下限的存在
3.所有大小為s的電路都能用subexp大小的branching program模擬
4.若能將模擬壓縮到O(t^ε)空間則P≠PSPACE可望被證明
5.對於d維圖靈機，時間t可用空間O((tlogt)^(1-1/(d+1)))模擬完成
6.若能證明Tree Evaluation問題可用LOGSPACE解，空間上限可降為O(√t)
此結果提供了攻克P vs PSPACE問題的新路徑也為P/NP問題帶來啟發
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.253.136.94 (臺灣)
※ 作者: jackliao1990 2025-05-23 19:43:40
※ 文章代碼(AID): #1eC5zloB (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1748000623.A.C8B.html
推 FannWong: 跟樓下想的一樣1F 1.165.26.20 台灣 05/23 19:44
推 moy5566: 恩恩跟我想的方向差不多3F 115.129.128.11 澳大利亞 05/23 19:44
※ 編輯: jackliao1990 (111.253.136.94 臺灣), 05/23/2025 19:45:09
→ WolfTeacher: 碩班跟教授說要這個 結果把我轟出研究室4F 101.10.10.96 台灣 05/23 19:44
→ syura945: pspice6F 114.137.119.96 台灣 05/23 19:45
→ kent: 幹 這我國小科展題目而已9F 111.249.160.101 台灣 05/23 19:46
推 ridecule: 太難了10F 114.39.123.25 台灣 05/23 19:46
推 BIGBBB: 這沒很難啊11F 122.121.208.179 台灣 05/23 19:47
推 rogher3399: 工三小12F 94.156.205.224 愛爾蘭 05/23 19:50
--