en fr Linear Logic and Sub-polynomial Classes of Complexity Logique linéaire et classes de complexité sous-polynomiales Report as inadecuate




en fr Linear Logic and Sub-polynomial Classes of Complexity Logique linéaire et classes de complexité sous-polynomiales - Download this document for free, or read online. Document in PDF available to download.

1 L.C.R. LIPN - Laboratoire d-Informatique de Paris-Nord

Abstract : This research in Theoretical Computer Science extends the gateways between Linear Logic and Complexity Theory by introducing two innovative models of computation. It focuses on sub-polynomial classes of complexity: AC and NC -the classes of efficiently parallelizable problems- and L and NL -the deterministic and non-deterministic classes of problems efficiently solvable with low resources on space. Linear Logic is used through its Proof Net presentation to mimic with efficiency the parallel computation of Boolean Circuits, including but not restricted to their constant-depth variants. In a second moment, we investigate how operators on a von Neumann algebra can be used to model computation, thanks to the method provided by the Geometry of Interaction, a subtle reconstruction of Linear Logic. This characterization of computation in logarithmic space with matrices can naturally be understood as a wander on simple structures using pointers, parsing them without modifying themWe make this intuition formal by introducing Non Deterministic Pointer Machines and relating them to other well-known pointer-like-machines. We obtain by doing so new implicit characterizations of sub-polynomial classes of complexity.

Résumé : Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables NC et AC et celle des problèmes solutionnables avec peu d-espace, dans ses versions déterministes et non-déterministes L et NL. La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s-inspire de la géométrie de l-interaction, une délicate reconstruction de la logique linéaire à l-aide d-opérateurs d-une algèbre de von Neumann. Nous détaillons comment l-interaction d-opérateurs représentant des entiers et d-opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d-autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.

en fr

Keywords : Complexity Geometry of Interaction Linear Logic Operator Algebra Alternating Turing Machines Boolean Circuits Uniformity Proof Nets

Mots-clés : Uniformité Réseaux de Preuves Logique Linéaire Complexité Géométrie de l-interaction Algèbre d-opérateur Machines de Turing Alternantes Circuits Booléens





Author: Clément Aubert -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents