Doctoral thesis
OA Policy
English

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

ContributorsGasperin, Anthony
DirectorsRolim, Jose
Defense date2014-07-03
Abstract

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.

Citation (ISO format)
GASPERIN, Anthony. Through group theory and topology, a contribution to computation and complexity theory. Doctoral Thesis, 2014. doi: 10.13097/archive-ouverte/unige:39876
Main files (1)
Thesis
accessLevelPublic
Identifiers
716views
242downloads

Technical informations

Creation27/08/2014 14:17:00
First validation27/08/2014 14:17:00
Update time14/03/2023 21:34:01
Status update14/03/2023 21:34:01
Last indexation30/10/2024 19:54:01
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack