David Eppstein 於 2025 年在 Journal of Information Processing 發表〈Computational Complexities of Folding〉，研究摺紙摺痕圖的可摺性、摺疊狀態重組與相關計算問題。論文證明若干問題具有高度計算複雜度，例如某些可重組摺紙從一個平摺狀態移動到另一狀態的決策問題是 PSPACE-complete；某些計數問題屬於 p-complete；特定自相似無限摺痕圖的平摺性甚至不可判定。
這些結果不是說「實際摺紙做不到」，而是說一般化後的數學問題可能沒有高效率的通用演算法。對設計者而言，這突顯了折痕圖的局部規則、層數、面鄰接關係與整體運動路徑之間存在複雜互動。
思與行
- 將「能否摺疊」、「怎麼摺」、「摺疊時會不會碰撞」與「如何在兩個狀態間轉換」分成不同問題。
- 在設計流程中先限制模型類別與自由度，避免以為單一演算法可解所有摺紙問題。
- 延伸閱讀摺紙的折痕圖是幾何拓樸與運動規劃的交界與計算複雜度提醒我們一般摺紙設計不會有萬用捷徑。
參考
- David Eppstein, “Computational Complexities of Folding,” Journal of Information Processing 33, 2025, pp. 954–973. J-STAGE 開放全文；DOI