The Stochastic Arrival Problem
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914948848812032 |
|---|---|
| author | Webster, Thomas |
| author_facet | Webster, Thomas |
| contents | We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is \PP{}-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_12982 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Stochastic Arrival Problem Webster, Thomas Computational Complexity We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is \PP{}-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm. |
| title | The Stochastic Arrival Problem |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2211.12982 |