Document Open Access Logo

Average-Case Completeness in Tag Systems

Authors Matthew Cook, Turlough Neary

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.20.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Matthew Cook
  • University of Zürich, Switzerland
  • ETH Zürich, Switzerland
Turlough Neary
  • University of Zürich, Switzerland
  • ETH Zürich, Switzerland

Funding

  • Neary, Turlough: Supported by Swiss National Science Foundation grant numbers 200021-153295 and 200021-166231.

Cite As Get BibTex

Matthew Cook and Turlough Neary. Average-Case Completeness in Tag Systems. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.20

Abstract

To prove average-case NP-completeness for a problem, we must choose a known average-case complete problem and reduce it to that problem. Unfortunately, the set of options to choose from is far smaller than for standard (worst-case) NP-completeness. In an effort to help remedy this we focus on tag systems, which due to their extreme simplicity have been a target for other types of reductions for many problems including the matrix mortality problem, the Post correspondence problem, the universality of cellular automaton Rule 110, and all of the smallest universal single-tape Turing machines. Here we show that a tag system can efficiently simulate a Turing machine even when the input is provided in an extremely simple encoding which adds just log n carefully set bits to encode an arbitrary Turing machine input of length n. As a result we show that the bounded halting problem for nondeterministic tag systems is average-case NP-complete. This result is unexpected when one considers that in the current state of the art for simple universal systems it had appeared that there was a trade-off whereby simpler systems required more complicated input encodings. In other words, although simple systems can compute interesting things, they had appeared to require very carefully encoded inputs in order to do so. Our result surprisingly goes in the opposite direction by giving the first average-case completeness result for such a simple model of computation. In ongoing work we have already found applications of our result having used it to give average-case NP-completeness results for a 2D generalization of the Collatz function, a nondeterministic version of the 2D elementary functions studied by Koiran and Moore, 3D piecewise affine maps, and bounded Post correspondence problem instances that use simpler word pairs than previous results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • average-case NP-completeness
  • encoding complexity
  • tag system
  • bounded halting problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andreas Blass and Yuri Gurevich. Matrix Transformation Is Complete for the Average Case. SIAM Journal on Computing, 24(1):3-29, 1995. URL: http://dx.doi.org/10.1137/S0097539792232070.
  2. Vincent D Blondel and John N Tsitsiklis. A survey of computational complexity results in systems and control. Automatica, 36:1249-1274, 2000. URL: http://dx.doi.org/10.1016/S0005-1098(00)00050-9.
  3. Andrej Bogdanov and Luca Trevisan. Average-Case Complexity. CoRR, abs/cs/0606037, 2006. URL: http://arxiv.org/abs/cs/0606037.
  4. Matthew Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1-40, 2004. URL: http://www.complex-systems.com/abstracts/v15_i01_a01.html.
  5. Matthew Cook and Turlough Neary. A New Proof of Average Case NP-Completeness for the Post Correspondence Problem. In preparation. Google Scholar
  6. Matthew Cook and Turlough Neary. Universality and Average-Case NP-Completeness in 2D Collatz Functions and Piecewise Affine Functions. In preparation. Google Scholar
  7. Jens Eisert, Markus P Müller, and Christian Gogolin. Quantum measurement occurrence is undecidable. Physical Review Letters, 108(26):260501, 2012. URL: http://dx.doi.org/10.1103/PhysRevLett.108.260501.
  8. Yuri Gurevich. Average case completeness. Journal of Computer and System Sciences, 42:346-398, 1991. URL: http://dx.doi.org/10.1016/0022-0000(91)90007-R.
  9. Tero Harju and Maurice Margenstern. Splicing systems for universal Turing machines. In DNA Computing, 10^th International Workshop on DNA Computing(2004), volume 3384 of Lecture Notes in Computer Science, pages 149-158. Springer, 2005. URL: http://dx.doi.org/10.1007/11493785_13.
  10. Pascal Koiran and Cristopher Moore. Closed-form analytic maps in one and two Dimensions can simulate universal Turing machines. Theoretical Computer Science, 210(1):217-223, 1999. URL: http://dx.doi.org/10.1016/S0304-3975(98)00117-0.
  11. Leonid Levin. Average case complete problems. SIAM Journal on Computing, 15(1):285-1286, 1986. URL: http://dx.doi.org/10.1137/0215020.
  12. Kristian Lindgren and Mats G. Nordahl. Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems, 4(3):299-318, 1990. URL: http://www.complex-systems.com/abstracts/v04_i03_a04.html.
  13. Yuri Matiyasevich and Géraud Sénizergues. Decision problems for semi-Thue systems with a few rules. Theoretical Computer Science, 330(2):145-169, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2004.09.016.
  14. Marvin Minsky. Size and structure of universal Turing machines using tag systems. In Recursive Function Theory, Symposium in Pure Mathematics, volume 5, pages 229-238, Provelence, 1962. AMS. Google Scholar
  15. Turlough Neary. Small universal Turing machines. PhD thesis, Department of Computer Science, National University of Ireland, Maynooth, 2008. Google Scholar
  16. Turlough Neary. Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS, volume 30 of LIPIcs, pages 649-661, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.649.
  17. Turlough Neary and Damien Woods. P-completeness of cellular automaton Rule 110. In International Colloquium on Automata, Languages and Programming 2006, (ICALP) Part I, volume 4051 of Lecture Notes in Computer Science, pages 132-143. Springer, 2006. URL: http://dx.doi.org/10.1007/11786986_13.
  18. Emil Post. Formal reductions of the general combinatorial decision problem. American Journal of Mathematics, 65(2):197-215, 1943. URL: http://dx.doi.org/10.2307/2371809.
  19. Raphael Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12(3):177-209, 1971. URL: http://dx.doi.org/10.1007/BF01418780.
  20. Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, 1996. URL: http://dx.doi.org/10.1016/S0304-3975(96)00077-1.
  21. Yurii Rogozhin and Sergey Verlan. On the rule complexity of universal tissue P systems. In Sixth international Workshop on Membrane Computing(2005), volume 3850 of Lecture Notes in Computer Science, pages 356-362. Springer, 2006. URL: http://dx.doi.org/10.1007/11603047_24.
  22. Paul Rothemund. A DNA and restriction enzyme implementation of Turing Machines. In DNA Based Computers: Proceeding of a DIMACS Workshop, volume 2055, pages 75-119. AMS, 1996. URL: https://authors.library.caltech.edu/27384/.
  23. Hava Siegelmann and Maurice Margenstern. Nine switch-affine neurons suffice for Turing universality. Neural Networks, 12:593-600, 1999. URL: http://dx.doi.org/10.1016/S0893-6080(99)00025-8.
  24. Hava Siegelmann and Eduardo Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50(1):132-150, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1013.
  25. Jie Wang. Average-case computational complexity theory. In Lane A Hemaspaandra and Alan L Selman, editors, Complexity theory retrospective II, pages 295-328. Springer-Verlag, 1998. Google Scholar
  26. Damien Woods and Turlough Neary. On the time complexity of 2-tag systems and small universal Turing machines. In In 47^th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 132-143, Berkeley, California, October 2006. IEEE. URL: http://dx.doi.org/10.1109/FOCS.2006.58.
  27. Adam Yedidia and Scott Aaronson. A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. Complex Systems, 25(4):297-237, 2016. URL: http://www.complex-systems.com/abstracts/v25_i04_a04.html.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact