Paper by Erik D. Demaine

Byoungkwon An, Erik D. Demaine, Martin L. Demaine, and Jason S. Ku, “Computing 3SAT on a Fold-and-Cut Machine”, in Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), Ottawa, Ontario, Canada, July 26–28, 2017, to appear.

This paper introduces a computational model called a fold-and-cut machine which allows as operations simple folds and unfolds, straight-line cuts, and inspection for a through-hole (hole through all the layers of paper). We show that a (deterministic) fold-and-cut machine can decide a 3SAT instance with n variables and m clauses using O(n m + m2) operations (with just one cut and inspection), showing that the machine is at least as powerful as a nondeterministic Turing machine.

The paper is 6 pages.

The paper is available in PDF (302k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated September 3, 2017 by Erik Demaine.