On Randomized Computational Models and Complexity Classes: a Historical Overview
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916399885058048 |
|---|---|
| author | Antonelli, Melissa Lago, Ugo Dal Pistone, Paolo |
| author_facet | Antonelli, Melissa Lago, Ugo Dal Pistone, Paolo |
| contents | Since their appearance in the 1950s, computational models capable of performing probabilistic choices have received wide attention and are nowadays pervasive in almost every areas of computer science. Their development was also inextricably linked with inquiries about computation power and resource issues. Although most crucial notions in the field are well-known, the related terminology is sometimes imprecise or misleading. The present work aims to clarify the core features and main differences between machines and classes developed in relation to randomized computation. To do so, we compare the modern definitions with original ones, recalling the context in which they first appeared, and investigate the relations linking probabilistic and counting models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11999 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Randomized Computational Models and Complexity Classes: a Historical Overview Antonelli, Melissa Lago, Ugo Dal Pistone, Paolo Logic in Computer Science Since their appearance in the 1950s, computational models capable of performing probabilistic choices have received wide attention and are nowadays pervasive in almost every areas of computer science. Their development was also inextricably linked with inquiries about computation power and resource issues. Although most crucial notions in the field are well-known, the related terminology is sometimes imprecise or misleading. The present work aims to clarify the core features and main differences between machines and classes developed in relation to randomized computation. To do so, we compare the modern definitions with original ones, recalling the context in which they first appeared, and investigate the relations linking probabilistic and counting models. |
| title | On Randomized Computational Models and Complexity Classes: a Historical Overview |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2409.11999 |