Abstract
To prove averagecase NPcompleteness for a problem, we must choose a known averagecase complete problem and reduce it to that problem. Unfortunately, the set of options to choose from is far smaller than for standard (worstcase) NPcompleteness. 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 singletape 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 averagecase NPcomplete. 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 tradeoff 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 averagecase 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 averagecase NPcompleteness 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.
BibTeX  Entry
@InProceedings{cook_et_al:LIPIcs:2019:10259,
author = {Matthew Cook and Turlough Neary},
title = {{AverageCase Completeness in Tag Systems}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {20:120:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10259},
doi = {10.4230/LIPIcs.STACS.2019.20},
annote = {Keywords: averagecase NPcompleteness, encoding complexity, tag system, bounded halting problem}
}
Keywords: 

averagecase NPcompleteness, encoding complexity, tag system, bounded halting problem 
Collection: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 
Issue Date: 

2019 
Date of publication: 

12.03.2019 