[爆卦] "P vs PSPACE問題"半世紀以來最大進展

[jackliao1990 (j)]

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 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1748000623.A.C8B.html
推 FannWong: 跟樓下想的一樣
推 derrick1220: 講人話林北文組
推 moy5566: 恩恩跟我想的方向差不多
※ 編輯: jackliao1990 (111.253.136.94 臺灣), 05/23/2025 19:45:09
→ WolfTeacher: 碩班跟教授說要這個 結果把我轟出研
→ WolfTeacher: 究室
→ syura945: pspice
推 lianpig5566: 這我高中就做過了
推 magic833133: 有中文翻譯嗎
→ kent: 幹 這我國小科展題目而已
推 ridecule: 太難了
推 BIGBBB: 這沒很難啊
推 rogher3399: 工三小
推 a34567: ???
推 Rron1976: 我只認得psp
推 carwho: 這不難啦 小時候大家都有想過吧
推 p2p8ppp: 這題我會  p = 0 or n = 1
推 kimuya1127: 這誰不知道,大家都會吧...
推 madaofreak: 威廉斯也太坎坷 課堂被說沒天賦該轉行
→ madaofreak:  申請博班還被拒絕==
推 bye2007: P = NP？
推 b2305911: 我懂 就是V=IR
推 leechiungyi: 咳咳咳我看不懂，但我愛民進黨
推 cuteme5566: PIMBA
推 khastw: 可是P≠Pspace和P≠NP不會有關連阿
→ khastw: 研究這個好像...何必呢?
推 khastw: 當然我是說如果是想以此做P≠NP的敲門磚的
→ khastw: 話
推 TheZealot: 沒錯 跟我算出來ㄉ一樣