Research NewsMathematics

Proving a Link Between Logic and Origami

See allHide authors and affiliations

Science  06 Feb 1998:
Vol. 279, Issue 5352, pp. 804-805
DOI: 10.1126/science.279.5352.804

You are currently viewing the summary.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution


BALTIMORE-- A pair of computer scientists has shown that a well-known origami problem called the flat-folding problem belongs to a class of tasks so difficult that each contains the key to solving--or being unable to solve--all the rest. The problem, predicting whether an origami model can be folded flat without creating any new creases or otherwise damaging it, has long tantalized the small community that studies the mathematics underlying origami. Now these scientists have shown that this question is equivalent to a famous "hard" problem in computer science known as not-all-true 3-SAT.