Randomness and completeness in computational complexity
This book contains a revised version of the dissertation the author wrote at the Department of Computer Science of the University of Chicago. The thesis was submitted to the Faculty of Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was honored with the 1999...
Sábháilte in:
| Príomhchruthaitheoir: | |
|---|---|
| Formáid: | Livre numérique |
| Teanga: | Anglais |
| Foilsithe / Cruthaithe: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Sraith: | Lecture notes in computer science
1950 |
| Ábhair: | |
| Rochtain ar líne: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Nóta: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Randomness and completeness in computational complexity, Dieter van Melkebeek, 2000, New York, Springer, 1 vol. (XV-196 p.), Lecture notes in computer science, 3-540-41492-4 • Randomness and Completeness in Computational Complexity, Texte imprimé, 9783662202166 |
| LEADER | 03843nam a22003857a 4500 | ||
|---|---|---|---|
| 001 | 949209 | ||
| 008 | 110927q2000 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN155221264 | ||
| 020 | |a 9783540445456 (PDF) | ||
| 041 | 0 | |a eng | |
| 082 | |a 004.0151 | ||
| 082 | |a 004 | ||
| 100 | 1 | |a Van Melkebeek, Dieter. | |
| 245 | 1 | 0 | |a Randomness and completeness in computational complexity |c Dieter van Melkebeek. |
| 260 | |a Berlin [etc.] : |b Springer. | ||
| 260 | |a Cham : |b Springer Nature, |c [20..]. | ||
| 490 | 0 | |a Lecture notes in computer science |v 1950 |x 1611-3349 | |
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 505 | 0 | |a 1. Introduction -- 2. Preliminaries -- 3. Derandomizing Arthur-Merlin Games -- 4. Sparseness of Complete Languages -- 5. Autoreducibility of Complete Languages -- 6. The Size of Randomized Polynomial Time -- 7. The Frequency of Complete Languages -- 8. The Frequency of Autoreducible Languages. | |
| 506 | |a Accès en ligne pour les établissements français bénéficiaires des licences nationales | ||
| 506 | |a Accès soumis à abonnement pour tout autre établissement | ||
| 506 | |a Conditions particulières de réutilisation pour les bénéficiaires des licences nationales. https://www.licencesnationales.fr/springer-nature-ebooks-contrat-licence-ln-2017 | ||
| 520 | |a This book contains a revised version of the dissertation the author wrote at the Department of Computer Science of the University of Chicago. The thesis was submitted to the Faculty of Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was honored with the 1999 ACM Doctoral Dissertation Award in May 2000. Summary Computational complexity is the study of the inherent di culty of compu- tional problems and the power of the tools we may use to solve them. It aims to describe how many resources we need to compute the solution as a function of the problem size. Typical resources include time on sequential and parallel architectures and memory space. As we want to abstract away from details of input representation and speci cs of the computer model, we end up with classes of problems that we can solve within certain robust resource bounds such as polynomial time, parallel logarithmic time, and logarithmic space. Research in complexity theory boils down to determining the relationships between these classes { inclusions and separations. In this dissertation, we focus on the role of randomness and look at various properties of hard problems in order to obtain separations. We also investigate the power of nondeterminism and alternation, as well as space versus time issues. Randomness provides a resource that seems to help in various situations. | ||
| 650 | |a Informatique | ||
| 650 | |a Algorithmes | ||
| 650 | |a Complexité de calcul (informatique) | ||
| 650 | |a Informatique |x Mathématiques | ||
| 776 | 0 | |0 054351898 |t Randomness and completeness in computational complexity |f Dieter van Melkebeek |d 2000 |c New York |n Springer |p 1 vol. (XV-196 p.) |s Lecture notes in computer science |z 3-540-41492-4 | |
| 776 | 0 | |t Randomness and Completeness in Computational Complexity |b Texte imprimé |z 9783662202166 | |
| 856 | 4 | |q PDF |u https://doi.org/10.1007/3-540-44545-5 |z Accès sur la plateforme de l'éditeur | |
| 856 | 4 | |u https://revue-sommaire.istex.fr/ark:/67375/8Q1-48NPRD1L-0 |z Accès sur la plateforme Istex | |
| 856 | 4 | |5 452349901:748060596 |u https://ezproxy.univ-orleans.fr/login?url=https://doi.org/10.1007/3-540-44545-5 |z Accès Université d'Orléans | |
| 856 | 4 | |5 180339901:751512117 |u https://ezproxy.insa-cvl.fr/login?qurl=https://doi.org/10.1007/3-540-44545-5 |z Accès INSA CVL | |
| 997 | |0 949209 |1 Livre numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||