  Why is it difficult to refold a previously folded sheet of paper? We show
that even crease patterns with only one designed folding motion inevitably
contain an exponential number of `distractor' folding branches accessible from
a bifurcation at the flat state. Consequently, refolding a sheet requires
finding the ground state in a glassy energy landscape with an exponential
number of other attractors of higher energy, much like in models of protein
folding (Levinthal's paradox) and other NP-hard satisfiability (SAT) problems.
As in these problems, we find that refolding a sheet requires actuation at
multiple carefully chosen creases. We show that seeding successful folding in
this way can be understood in terms of sub-patterns that fold when cut out
(`folding islands'). Besides providing guidelines for the placement of active
hinges in origami applications, our results point to fundamental limits on the
programmability of energy landscapes in sheets.
