caa a22 4500 569311640 20200218075016.0 cr unu---uuuuu 190727s2019 xx s 100 0 eng 10.3929/ethz-b-000352453 doi 10.4230/LIPIcs.STACS.2019.20 doi (ETHRESEARCH)oai:www.research-collection.ethz.ch:20.500.11850/352453 Cook Matthew Average-Case Completeness in Tag Systems [Elektronische Daten] [Matthew Cook, Turlough Neary, Rolf Niedermeier (Editor), Christophe Paul (Editor)] Leibniz int. proc. inform. Wadern Schloss Dagstuhl-Leibniz-Zentrum für Informatik 2019 17 p. Open access ethresearch 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. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) in Dagstuhl, Germany (March 13-16, 2019) Creative Commons Attribution 3.0 Unported http://creativecommons.org/licenses/by/3.0 ethresearch Average-case NP-completenes ethresearch Encoding complexity ethresearch Tag system ethresearch Bounded halting problem ethresearch Neary Turlough joint author Niedermeier Rolf Editor edt Paul Christophe Editor edt 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) Wadern : Schloss Dagstuhl-Leibniz-Zentrum für Informatik p. 20 978-3-95977-100-9 http://hdl.handle.net/20.500.11850/352453 text/html WWW-Backlink auf das Repository (Open access) 1 Conference Paper ethresearch ETHRESEARCH 856 40 http://hdl.handle.net/20.500.11850/352453 text/html WWW-Backlink auf das Repository (Open access) ETHRESEARCH 100 1- Cook Matthew ETHRESEARCH 700 1- Neary Turlough joint author ETHRESEARCH 700 1- Niedermeier Rolf Editor edt ETHRESEARCH 700 1- Paul Christophe Editor edt ETHRESEARCH 773 0- 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) Wadern : Schloss Dagstuhl-Leibniz-Zentrum für Informatik p. 20 978-3-95977-100-9 SWISSBIB 569311640 BK010053 XK010053 XK010000 ETHRESEARCH ETHRESEARCH ETHRESEARCH Conference Paper Open access