One-Clock Priced Timed Games are PSPACE-hard

14^th April 2020, 11:00
Rasmus Ibsen-Jensen

Abstract

The talk is about my recent result (with John Fearnley & Rahul Savani) on one-clock priced timed games, showing the first complexity lower bound (beyond P). The paper show that they are PSPACE-hard (the talk will only show NP- and coNP-hardness though) and that the value function (which are an piecewise linear function) consists of an exponential number of line pieces. The lower bound also applies in some special cases. As positive results, we show that trees and undirected graphs are in P.

Based on joint work with John Fearnley & Rahul Savani
See https://arxiv.org/abs/2001.04458
To appear in LICS'20

Additional Materials

• https://arxiv.org/abs/2001.04458