Le produit direct de fonctions et les programmes de branchement avec oracle

Abstract

Ce mémoire explore divers résultats de la littérature à propos du produit direct de fonctions. Plus précisément, on retrouve la production de masse, le multi-calcul et l’espace catalytique. Le lien entre ces trois variantes du produit direct de fonctions est établi explicitement pour la première fois. La production de masse permet l’économie de ressources lors du calcul d’une fonction à plusieurs reprises sur des entrées différentes. On reprend en détails une borne de la littérature sur la taille des circuits qui calculent une fonction un nombre de fois qui ex- cède tout polynôme. Le multi-calcul permet l’économie de ressources lors du calcul d’une multitude de fonctions sur la même entrée. L’espace catalytique est une combinaison des restrictions de la production de masse et du multi-calcul. Il s’agit du calcul d’une fonction une multitude de fois sur la même entrée. L’espace catalytique est étudié en utilisant des machines de Turing dont une partie de la mémoire doit être rétablie à son contenu initial. On reprend en détails un résultat de la littérature montrant l’inclusion de la classe TC 1 dans l’espace catalytique logarithmique. Dans la deuxième partie de ce mémoire, notre contribu- tion est une nouvelle forme de programme de branchement. À partir de celle-ci, on présente plusieurs langages paramétriques. Une analyse est faite pour montrer la coNP-complétude de l’un de ces langages.

This dissertation explores various results from the literature about the direct product of functions. We discuss mass production, multi-computation and catalytic space. We ex- plicitely show for the first time the link these three variants of the direct product of func- tions. Mass production allows economy of resources during the computation of a function on multiple inputs. We present a bound on the size of circuits which compute a function a super-polynomial number of times. With multi-computation, we can represent sharing of resources when computing multiple functions over the same input. The last one, cat- alytic space, is the intersection of mass production and multi-computation. A computation in catalytic space is computing a function multiple times over the same input. We study the catalytic space with Turing machines whose part of their memory needs to be restore to its initial content. We present in detail the result from the literature which shows the inclusion of TC 1 in the logarithmic catalytic space. In the second section, we contribute with a new family of branching programs. We then derive parametric languages. We prove that one of them is coNP-complete.