- Computational complexities of folding.
D. Eppstein.
Invited talk, 8th International Meeting on Origami in Science, Mathematics and Education, Melbourne, Australia, 2024.
Invited talk, 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2024.
arXiv:2410.07666.
Journal of Information Processing 33: 954–973, 2025.We survey known hardness results on folding origami and prove several new ones: finding a flat-folded state is \(\mathsf{NP}\)-hard, but fixed-parameter tractable in a combination of ply and the treewidth of an associated graph. Finding a 3d-folded state cannot be expressed in closed form and cannot be computed by bounded-degree algebraic-root primitives. Reconfiguring certain systems of overlapping origami squares, hinged to a table at one edge, is \(\mathsf{PSPACE}\)-complete, and counting the number of configurations is \(\#\mathsf{P}\)-complete. Testing flat-foldability of infinite fractal folding patterns (even on normal square origami paper) is undecidable.