Through group theory and topology, a contribution to computation and complexity theory

Diplôme Thèse Through group theory and topology, a contribution to computation and complexity theory eng 2014-07-03 author Gasperin Anthony 679831 director Rolim Jose 27265 10.13097/archive-ouverte/unige:39876 urn:nbn:ch:unige-398769 Sc. 4702 The formal study of algorithms arises with the definition of the Turing machine in a context which is disjoint from the classical mathematical framework. The Turing machine allows one to define and study different classes of algorithms considering their time and space complexity. However even if the Turing machine model and its related tools give a formal framework for the study of algorithms it seems that it is limited. Indeed there exists still old problems which can be stated easily for which the theory cannot provide an answer. Such considerations led to the development of independent characterization of complexity classes. In particular finite model theory gives an interesting framework to characterize some important complexity classes. Recently a method developed by Sapir, Birget and Rips allows one to construct a group that simulates the working of a Turing machine. Therefore it allows one to think computation from a dissident point of view using the tools one can find in the framework related to group theory. Sapir and Olshanskii suggests that the topology of asymptotic cones of S-machines, interpreted as groups, could characterize some properties of S-machine. Our work considers the point of view of Sapir and Olshanskii and using the tools available in this new context tries to understand the nature of the link. In a first time we shall consider an independent construction of a group that simulates an algorithm for a well-known problem. Using some results of Sapir and Olshanskii we shall conclude that the topology of asymptotic cones of the group constructed is always broken by some transition rules considered in the algorithm, we shall also describe the nature of such computations in the group. In a second time we use the bipartite chords invariant developed by Sapir and Olshanksii and show that it can be use to correct the behaviour noticed. Then we shall consider the whole construction of Sapir, Birget and Rips and conclude that a part of the algorithm embedded in every group constructed has consequences on the topology of the asymptotic cones. Finally, we shall embed our study in a more general context, that is the context of metric space. We shall also notice that the construction of metric spaces from algorithms that belong to different complexity classes has a consequence on the topology of the asymptotic cones. Dewey 025.063 13 Centre universitaire d'informatique 0D3 32 Département d'informatique 18 false 94888c11-c4fd-440c-b5f8-07f57cf3a3c6 Thesis Public Thesis.pdf 704847 application/pdf openAccess Centres et instituts / Centre universitaire d'informatique Faculté des sciences / Département d'informatique

Title	Published in	Access level	OA Policy	Year	Views	Downloads

Through group theory and topology, a contribution to computation and complexity theory				2014	772	260

Archive ouverte UNIGE

Gasperin, Anthony