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
Last updated October 17, 2021 by