Follow

Rigid Foldability is NP-Hard: arxiv.org/abs/1812.01160

It was previously known that folding a purported origami folding pattern to a flat state is NP-hard, because you can encode logic in the way the paper gets in the way of itself. But this paper proves that it's hard even to tell whether you can make any rigid motion at all starting from completely unfolded paper, well before self-interference kicks in. Instead, the difficulty involves getting sums of angles to come out right.

Sign in to participate in the conversation
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.