Cette thèse est consacrée à la complexité basée sur le paradigme des preuves interactives.
Les classes ainsi définies ont toutes en commun qu’un ou plusieurs prouveurs,
infiniment puissants, tentent de convaincre un vérificateur, de puissance bornée, de
l’appartenance d’un mot à un langage. Nous abordons ici le modèle classique, où les
participants sont des machines de Turing, et le modèle quantique, où ceux-ci sont
des circuits quantiques. La revue de littérature que comprend cette thèse s’adresse
à un lecteur déjà familier avec la complexité et l’informatique quantique.
Cette thèse présente comme résultat la caractérisation de la classe NP par une
classe de preuves interactives quantiques de taille logarithmique.
Les différentes classes sont présentées dans un ordre permettant d’aborder aussi
facilement que possible les classes interactives. Le premier chapitre est consacré aux
classes de base de la complexité ; celles-ci seront utiles pour situer les classes subséquemment
présentées. Les chapitres deux et trois présentent respectivement les
classes à un et à plusieurs prouveurs. La présentation du résultat ci-haut mentionné
est l’objet du chapitre quatre. / This thesis is devoted to complexity theory based on the interactive proof paradigm.
All classes defined in this way involve one or many infinitely powerful provers
attempting to convince a verifier of limited power that a string belongs to a certain
language. We will consider the classical model, in which the various participants
are Turing machines, as well as the quantum model, in which they are quantum
circuits. The literature review included in this thesis assume that the reader is
familiar with the basics of complexity theory and quantum computing.
This thesis presents the original result that the class NP can be characterized
by a class of quantum interactive proofs of logarithmic size.
The various classes are presented in an order that facilitates the treatment of
interactive classes. The first chapter is devoted to the basic complexity classes;
these will be useful points of comparison for classes presented subsequently. Chapters
two and three respectively present classes with one and many provers. The
presentation of the result mentioned above is the object of chapter four.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/3567 |
| Date | 07 1900 |
| Creators | Blier, Hugue |
| Contributors | Tapp, Alain |
| Source Sets | Université de Montréal |
| Language | French |
| Detected Language | French |
| Type | Thèse ou Mémoire numérique / Electronic Thesis or Dissertation |
Page generated in 0.0019 seconds