Paper by Erik D. Demaine

Reference:

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.

Abstract:

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 + m²) operations (with just one cut and inspection), showing that the machine is at least as powerful as a nondeterministic Turing machine.

Length:

The paper is 6 pages.

Availability:

The paper is available in PDF (302k).

See information on file formats.

[Google Scholar search]