還記得以前上李家同教授的演算法課時，印象最深刻的就是 NP 問題。
當時的理解是，這類問題最麻煩的地方，在於隨著問題規模增加，尋找答案所需要的計算時間可能呈現爆炸性成長。即使電腦運算能力不斷進步，面對足夠複雜的問題，仍然可能需要難以想像的時間才能解決。
這也讓我一直認為，某些 NP 困難問題的計算效率，似乎存在難以突破的極限。
最近看到 OpenAI 針對**指數時間假說（Exponential Time Hypothesis, ETH）**提出的新研究，讓我相當驚訝。
研究指出，某些過去被認為需要指數時間處理的 NP 困難問題，理論上可能存在更有效率的演算法，讓計算時間不必隨著問題規模以過去預期的速度增加。
當然，這不代表所有 NP 問題都能快速解決，更不代表 P = NP 已經獲得證明。
但這項研究最讓我感到震撼的，不只是演算法可能變得更快，而是過去在課堂上建立、認為難以突破的計算複雜度觀念，如今竟然有被重新檢視的可能。
科技與數學研究最迷人的地方，或許就是今天我們深信的極限，未來未必真的是極限。新的研究方向。
留言