Le produit direct de fonctions et les programmes de branchement avec oracle
Thèse ou mémoire / Thesis or Dissertation
Date de publication
Autrices et auteurs
Identifiant ORCID de l’auteur
Contributrices et contributeurs
Direction de recherche
Publié dans
Date de la Conférence
Lieu de la Conférence
Éditeur
Cycle d'études
Maîtrise / Master's
Programme
Affiliation
Mots-clés
- Théorie de la complexité
- Production de masse
- Programme de branchement
- Espace catalytique
- Complexity theory
- Branching program
- Catalytic space
- Mass production
Organisme subventionnaire
Résumé
Résumé
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.
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.
Table des matières
Notes
Notes
Autre version linguistique
Ensemble de données lié
Licence
Approbation
Évaluation
Complété par
Référencé par
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Sauf si le document est diffusé sous une licence Creative Commons, il ne peut être utilisé que dans le cadre d'une utilisation équitable et non commerciale comme le prévoit la Loi (i.e. à des fins d'étude privée ou de recherche, de critique ou de compte-rendu). Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.