Search Results

Documents authored by Neary, Turlough

Document
DOI: 10.4230/LIPIcs.STACS.2019.20
Average-Case Completeness in Tag Systems

Authors: Matthew Cook and Turlough Neary

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.STACS.2019.20,
  author =	{Cook, Matthew and Neary, Turlough},
  title =	{{Average-Case Completeness in Tag Systems}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.20},
  URN =		{urn:nbn:de:0030-drops-102590},
  doi =		{10.4230/LIPIcs.STACS.2019.20},
  annote =	{Keywords: average-case NP-completeness, encoding complexity, tag system, bounded halting problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.649
Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words

Authors: Turlough Neary

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Since Cocke and Minsky proved 2-tag systems universal, they have been extensively used to prove the universality of numerous computational models. Unfortunately, all known algorithms give universal 2-tag systems that have a large number of symbols. In this work, tag systems with only 2 symbols (the minimum possible) are proved universal via an intricate construction showing that they simulate cyclic tag systems. We immediately find applications of our result. We reduce the halting problem for binary tag systems to the Post correspondence problem for 5 pairs of words. This improves on 7 pairs, the previous bound for undecidability in this problem. Following our result, only the cases for 3 and 4 pairs of words remains open, as the problem is known to be decidable for 2 pairs. In a further application, we apply the reductions of Vesa Halava and others to show that the matrix mortality problem is undecidable for sets with six 3 x 3 matrices and for sets with two 18 x 18 matrices. The previous bounds for the undecidability in this problem was seven 3 x 3 matrices and two 21 x 21 matrices.
Cite as

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 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 649-661, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{neary:LIPIcs.STACS.2015.649,
  author =	{Neary, Turlough},
  title =	{{Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{649--661},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.649},
  URN =		{urn:nbn:de:0030-drops-49486},
  doi =		{10.4230/LIPIcs.STACS.2015.649},
  annote =	{Keywords: tag system, Post correspondence problem, undecidability}
}
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 Imprint Privacy Contact