One-Clock Priced Timed Games are PSPACE-hard

Fearnley, John, Ibsen-Jensen, Rasmus and Savani, Rahul ORCID: 0000-0003-1262-7831 (2020) One-Clock Priced Timed Games are PSPACE-hard. LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, abs/20. pp. 397-409.

Text
2001.04458v2.pdf - Author Accepted Manuscript
Download (464kB) | Preview

Official URL: http://dx.doi.org/10.1145/3373718.3394772

Abstract

The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponential number of event points. Both results hold even in very restricted classes of games such as DAGs with treewidth three. Finally, we provide a number of positive results, including polynomial-time algorithms for even more restricted classes of OCPTGs such as trees.

Item Type:	Article
Uncontrolled Keywords:	cs.GT, cs.GT, cs.FL, cs.LO
Depositing User:	Symplectic Admin
Date Deposited:	28 Apr 2020 10:26
Last Modified:	18 Jan 2023 23:54
DOI:	10.1145/3373718.3394772
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3084306