Project

NP completeness; time/space computational complexity; nondeterministic computation; models of computation; decidability/undecidability; small universal Turing machines; simple universal models of computation

Lead
Ein universelles Rechnermodell ist ein Modell, welches jedes algorithmisch lösbare Problem lösen kann. Ein gewöhnlicher Computer ein alltägliches Beispiel eines universellen Rechnermodells. Einfache universelle Modelle werden genutzt um Universalität anderer Modelle zu beweisen, die es erlauben zu bestimmen wie schwierig es ist das Verhalten einfacher Systeme vorherzusagen. Das Fehlen einfacher nichtdeterministischer Modelle in der Literatur ist überraschend, da Nichtdeterminismus für notwendig gehalten wird, um NP-vollständige Probleme effizient zu lösen, welche Probleme in vielen Forschungsgebieten beinhalten. Wir werden nichtdeterministische Varianten der einfachsten deterministischen Modelle konstruieren, um NP-Vollständigkeits Ergebnisse für einfache Systeme nachzuweisen. Unsere Modelle haben Anwendungen auf wichtige Probleme in der Mathematik und Informatik und wir versprechen uns Fortschritte zur Lösung dieser Probleme, indem wir uns diesen aus einer neuen Richtung nähern.
Lay summary
Das Verständnis der Beziehungen zwischen den Mengen P (Probleme die man mit deterministische Modellen effizient lösen kann) und NP (Probleme die man mit nicht-deterministischen Modellen effizient lösen kann) ist grundlegend zu bestimmen, welche Probleme von Computern gelöst werden können und welche nicht. Die Menge P beschreibt genau die Menge an (effizient) lösbaren Problemen auf Computern, und die Menge NP-vollständig (die härtesten Probleme in NP) sind vermutlich nicht (effizient) lösbar auf Computern. Die Menge NP-vollständig enthält häufige Optimierungs- und Suchprobleme, die in vielen Disziplinen und sogar im Alltag auftreten. Daher ist das Fehlen einfacher nichtdeterministischer Modelle in der Literatur überraschend. Die Suche nach einfachen universellen Rechnermodellen beruht oft auf Sequenzen von Simulationen zwischen Modellen. Zum Beispiel, die Universalität von Modell B kann durch Simulation von Modell A bewiesen werden und dadurch kann man die Universalität von Modell C durch die Simulation von Modell B aufzeigen. Solche  Simulationssequenzen bedeuten, dass Verbesserungen in einem Modell oft Anwendungen für viele andere Modelle findet. Zum Beispiel Verbesserungen der Effizienz von Modell A hinsichtlich Rechenzeit und Speicherverbrauch implizieren verbesserte Effizienz von Modell B und C. Wir werden nichtdeterministische Versionen von vielen der einfachsten bekannten Rechnermodelle finden und aufgrund der Simulationsketten zwischen diesen Modellen, werden unsere neuen nichtdeterministischen Modelle hilfreich sein für die Prüfung von NP-Vollständigkeits Ergebnissen vieler anderer einfachen Systeme und hat Auswirkungen auf grundlegende Probleme in der Mathematik und Informatik. Dieses Projekt wird einen Einblick in die Beziehung zwischen Determinismus und Nichtdeterminismus in einfachen Rechnermodellen geben und uns dabei helfen die Komplexität einer Reihe von bedeutenden Problemen der Informatik und Mathematik zu bestimmen.

Direct link to Lay Summary

Last update: 03.02.2017

Lead
A universal model of computation is a model that can solve any algorithmically solvable problem. Assuming expandable memory, an ordinary personal computer is an everyday example of a universal model of computation. Simple universal models have applications in proving universality results for other models which then allows one to determine how difficult it is to predict behavior in simple systems. The lack of simple nondeterministic models in the literature is surprising given that nondeterminism is believed necessary to efficiently solve NP-complete problems, which include problems frequently arising in a variety of research fields. We will construct nondeterministic variants of the simplest deterministic models and use them to prove NP-completeness results for simple systems. The models we will focus on have applications to longstanding open problems in mathematics and computer science and the work proposed here will make progress by approaching these problems from an new perspective.
Lay summary
Understanding the relationship between the sets P (problems efficiently solvable on deterministic models) and NP (problems efficiently solvable on nondeterministic models) is fundamental to determining what is and is not solvable with computers. The set P is exactly the set of problems (efficiently) solvable on computers, and the set NP-complete (the hardest problems in NP) are believed not to be (efficiently) solvable on computers. The set NP-complete contains many common optimization and search problems that occur in a variety of disciplines and even in everyday life, and so the evident lack of simple nondeterministic models in the literature is surprising. Finding simple universal models of computation frequently relies on chains of simulations between models. For example model B is proved universal by simulating model A and then model C is proved universal by simulating model B. In the literature for simple universal models there are many of these simulation chains producing a web of interconnected simulations. This means that improvements in one model often has applications to many others. For example, improvements in the efficiency of model A in terms of computing time and memory usage has the domino effect of giving corresponding improvements in the efficiency of models B and C.   We will find nondeterministic versions of many of the simplest known models of computation, and due to the existing web of interconnected simulations for these models our new nondeterministic models will have applications in proving NP-completeness results for many other simple systems and to problems of fundamental importance in mathematics and computer science. This project will provide insight into the relationship between determinism and nondeterminism in simple models of computation and will help us determine the complexity of a number of significant problems in computer science and mathematics.

Direct link to Lay Summary

Last update: 03.02.2017

Active participation

Number	Title	Start	Funding scheme

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.