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, pages 208–213.

BibTeX

@InProceedings{FoldCutMachine_CCCG2017,
  AUTHOR        = {Byoungkwon An and Erik D. Demaine and Martin L. Demaine and Jason S. Ku},
  TITLE         = {Computing 3SAT on a Fold-and-Cut Machine},
  BOOKTITLE     = {Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)},
  bookurl       = {http://2017.cccg.ca/},
  ADDRESS       = {Ottawa, Ontario, Canada},
  MONTH         = {July 26--28},
  YEAR          = 2017,
  PAGES         = {208--213},

  length        = {6 pages},
  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/AnDDK17},
}

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]