Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy

Søren Kristoffer Stiil Frederiksen; Peter Bro Miltersen

doi:10.1007/978-3-642-45030-3_43

Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy

Søren Kristoffer Stiil Frederiksen, Peter Bro Miltersen

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

We show that the value of a finite-state concurrent reachability game can be approximated to arbitrary precision in TFNP[NP], that is, in the polynomial time hierarchy. Previously, no better bound than PSPACE was known for this problem. The proof is based on formulating a variant of the state reduction algorithm for Markov chains using arbitrary precision floating point arithmetic and giving a rigorous error analysis of the algorithm.

Originalsprog	Engelsk
Titel	Algorithms and Computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings
Redaktører	Leizhen Cai, Siu-Wing Cheng , Tak-Wah Lam
Antal sider	11
Forlag	Springer VS
Publikationsdato	2013
Sider	457-467
ISBN (Trykt)	978-3-642-45029-7
ISBN (Elektronisk)	978-3-642-45030-3
DOI	https://doi.org/10.1007/978-3-642-45030-3_43
Status	Udgivet - 2013
Begivenhed	International Symposium on Algorithms and Computation - Hong Kong, Kina Varighed: 16 dec. 2013 → 18 dec. 2013 Konferencens nummer: 24

Konference

Konference	International Symposium on Algorithms and Computation
Nummer	24
Land/Område	Kina
By	Hong Kong
Periode	16/12/2013 → 18/12/2013

Navn	Lecture Notes in Computer Science
Vol/bind	8283
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-45030-3_43

Citationsformater

Frederiksen, S. K. S., & Miltersen, P. B. (2013). Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy. I L. Cai, S.-W. Cheng , & T.-W. Lam (red.), Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings (s. 457-467 ). Springer VS. https://doi.org/10.1007/978-3-642-45030-3_43

Frederiksen, Søren Kristoffer Stiil ; Miltersen, Peter Bro. / Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy. Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. red. / Leizhen Cai ; Siu-Wing Cheng ; Tak-Wah Lam. Springer VS, 2013. s. 457-467 (Lecture Notes in Computer Science, Bind 8283).

@inproceedings{273743e73608476bbb3d9ece61f99c60,

title = "Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy",

abstract = " We show that the value of a finite-state concurrent reachability game can be approximated to arbitrary precision in TFNP[NP], that is, in the polynomial time hierarchy. Previously, no better bound than PSPACE was known for this problem. The proof is based on formulating a variant of the state reduction algorithm for Markov chains using arbitrary precision floating point arithmetic and giving a rigorous error analysis of the algorithm.",

author = "Frederiksen, {S{\o}ren Kristoffer Stiil} and Miltersen, {Peter Bro}",

year = "2013",

doi = "10.1007/978-3-642-45030-3_43",

language = "English",

isbn = "978-3-642-45029-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer VS",

pages = "457--467 ",

editor = "Cai, {Leizhen } and {Cheng }, {Siu-Wing } and Lam, {Tak-Wah }",

booktitle = "Algorithms and Computation",

note = "International Symposium on Algorithms and Computation ; Conference date: 16-12-2013 Through 18-12-2013",

}

Frederiksen, SKS & Miltersen, PB 2013, Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy. i L Cai, S-W Cheng & T-W Lam (red), Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. Springer VS, Lecture Notes in Computer Science, bind 8283, s. 457-467 , International Symposium on Algorithms and Computation, Hong Kong, Kina, 16/12/2013. https://doi.org/10.1007/978-3-642-45030-3_43

Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy. / Frederiksen, Søren Kristoffer Stiil; Miltersen, Peter Bro.
Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. red. / Leizhen Cai; Siu-Wing Cheng ; Tak-Wah Lam. Springer VS, 2013. s. 457-467 (Lecture Notes in Computer Science, Bind 8283).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy

AU - Frederiksen, Søren Kristoffer Stiil

AU - Miltersen, Peter Bro

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - We show that the value of a finite-state concurrent reachability game can be approximated to arbitrary precision in TFNP[NP], that is, in the polynomial time hierarchy. Previously, no better bound than PSPACE was known for this problem. The proof is based on formulating a variant of the state reduction algorithm for Markov chains using arbitrary precision floating point arithmetic and giving a rigorous error analysis of the algorithm.

AB - We show that the value of a finite-state concurrent reachability game can be approximated to arbitrary precision in TFNP[NP], that is, in the polynomial time hierarchy. Previously, no better bound than PSPACE was known for this problem. The proof is based on formulating a variant of the state reduction algorithm for Markov chains using arbitrary precision floating point arithmetic and giving a rigorous error analysis of the algorithm.

U2 - 10.1007/978-3-642-45030-3_43

DO - 10.1007/978-3-642-45030-3_43

M3 - Article in proceedings

SN - 978-3-642-45029-7

T3 - Lecture Notes in Computer Science

SP - 457

EP - 467

BT - Algorithms and Computation

A2 - Cai, Leizhen

A2 - Cheng , Siu-Wing

A2 - Lam, Tak-Wah

PB - Springer VS

T2 - International Symposium on Algorithms and Computation

Y2 - 16 December 2013 through 18 December 2013

ER -

Frederiksen SKS, Miltersen PB. Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy. I Cai L, Cheng SW, Lam TW, red., Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. Springer VS. 2013. s. 457-467 . (Lecture Notes in Computer Science, Bind 8283). doi: 10.1007/978-3-642-45030-3_43