NP completeness; time/space computational complexity; nondeterministic computation; models of computation; decidability/undecidability; small universal Turing machines; simple universal models of computation
CookMatthew, NearyTurlough (2019), Average-Case Completeness in Tag Systems, in 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany.
Neary Turlough, Cook Matthew (2018), Generalized Tag Systems, in Reachability Problems 12th International Conference, RP 2018
, Springer International Publishing, Cham.
Neary Turlough (2017), 2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets, in Descriptional Complexity of Formal Systems, DCFS 2017
, Springer International Publishing, Cham.
Spanning 7 decades, the search for simple (Turing) universal models of computation has received the attention of many. Despite all this interest there had been little or no investigation into the resource efficiency of the simplest models of computation. To address this lack of knowledge we pioneered research into the resource efficiency of these systems and have exponentially improved the efficiency of many of the simplest known models of computation. So far, our research has involved the simulation of deterministic models and so nondeterminism has not yet been explored for many of the simplest known models of computation. Giving simple efficient nondeterministic models will, analogous to the applications for simple efficient deterministic models, allow us to find other efficient nondeterministic models and prove NP-completeness results for simpler systems. Finding simple models of computation frequently relies on a chain of simulations between models. For example, Cocke and Minsky proved 2-tag systems universal by simulating Turing machines (TMs) and then Minksy and others gave some of the smallest known universal TMs (UTMs) by simulating 2-tag systems. The literature extends this and other chains to a host of other systems producing a web of interconnected simulations that includes many undecidability/universality results, which means that improvements in one model often has applications to many others. For example, an exponential improvement in the time efficiency of tag systems had the domino effect of showing that many of the simplest known models of computation are efficient simulators of TMs and thus P-complete to predict. It turns out that there is a straightforward way to adapt our algorithm to show that nondeterministic 2-tag systems simulate NTMs in polynomial time and so can be used to show that nondeterministic variants of many other models are also efficient simulators of NTMs and thus are NP-complete to predict. As another example we can adapt the deterministic models in one of our more recent results to show that nondeterministic binary tag systems efficiently simulate NTMs and so the bounded Post correspondence problem for five pairs of words is NP-complete and the bounded zero-product (``matrix mortality'') problem is NP-complete for set with six 3x3 matrices and sets with two 15x15 matrices. Unfortunately, many of the deterministic algorithms for simple models cannot be adapted in such a straightforward way to give efficient nondeterministic simulations of NTMs. For example, the smallest UTMs do not lend themselves to such a straightforward conversion to efficient nondeterministic UTMs and so we need to come up with new algorithms to give nondeterministic UTMs. This will allow us to prove NP-completeness results for many of the systems the are proven universal by simulating these small UTMs.Another application of the introduction of nondeterminism would be to help in proving undecidability results. For example, proving that a certain type of nondeterministic generalised Collatz function simulates TMs would show that the zero-product mortality problem for 2x2 matrices is undecidable, a problem which has been open since 1977. In another related aim we will also look for models that are useful for proving average case NP-completeness results. Levin and Venkatesan use the small UTMs of Ikeno and Watanabe to prove average case completeness results for their graph coloring problems as the encoding used by all of the smaller UTMs are not suitable for their reductions to random inputs. Exploring nondeterminism in simple models of computation will allow us to give new NP-completeness results, approach longstanding open problems from a new perspective and give us the opportunity to explore the relationship between simple deterministic and nondeterministic models of computation.