Skip to main content

Research Repository

Advanced Search

Fine-Grained Complexity of Temporal Problems

Dabrowski, K.K.; Jonsson, P.; Ordyniak, S.; Osipov, G.; Calvanese, Diego; Erdem, Esra; Thielscher, Michael

Authors

K.K. Dabrowski

P. Jonsson

S. Ordyniak

G. Osipov

Diego Calvanese

Esra Erdem

Michael Thielscher



Abstract

Expressive temporal reasoning formalisms are essential for AI. One family of such formalisms consists of disjunctive extensions of the simple temporal problem (STP). Such extensions are well studied in the literature and they have many important applications. It is known that deciding satisfiability of disjunctive STPs is NP-hard, while the fine-grained complexity of such problems is virtually unexplored. We present novel algorithms that exploit structural properties of the solution space and prove, assuming the Exponential-Time Hypothesis, that their worst-case time complexity is close to optimal. Among other things, we make progress towards resolving a long-open question concerning whether Allen's interval algebra can be solved in single-exponential time, by giving a 2^{O(nloglog(n))} algorithm for the special case of unit-length intervals.

Citation

Dabrowski, K., Jonsson, P., Ordyniak, S., Osipov, G., Calvanese, D., Erdem, E., & Thielscher, M. (2020). Fine-Grained Complexity of Temporal Problems. . https://doi.org/10.24963/kr.2020/29

Conference Name KR 2020
Conference Location Rhodes, Greece
Start Date Sep 12, 2020
End Date Sep 18, 2020
Acceptance Date Jul 7, 2020
Publication Date 2020
Deposit Date Jul 10, 2020
Pages 284-293
Series ISSN 2334-1033
ISBN 9780999241172
DOI https://doi.org/10.24963/kr.2020/29

You might also like



Downloadable Citations