Map Folding
Created Donnerstag 25 Juli 2024
A flat folding of a piece of paper is a folding by creases into a multilayered but planar shape. The paper is permitted to touch but not to penetrate itself. A fundamental questionon flat folding is this:
Given a (rectangular) piece of paper marked with creases, with each subsegment marked as either a mountain or valley crease, does it have a flat folded state?
In 1996 the question was proven to be NP-hard, i.e. at least as intractable as an NP-complete problem.
Yet open question:
Given a (rectuangluar) piece of paper marked by a regular square grid of unit-separated creases, with each subsegment marked as either a mountain or a valley crease, can it be folded into a single 1×1 square?
Backlinks: Foldability Questions