Computational complexity of linear constraints over the integers
2013 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 0374-2539, Vol. 195, 44-62 p.Article in journal (Refereed) Published
Temporal reasoning problems arise in many areas of Al, including planning, natural language understanding, and reasoning about physical systems. The computational complexity of continuous-time temporal constraint reasoning is fairly well understood. There are, however, many different cases where discrete time must be considered; various scheduling problems and reasoning about sampled physical systems are two examples. Here, the complexity of temporal reasoning is not as well-studied nor as well-understood. In order to get a better understanding, we consider the powerful Horn disjunctive linear relations (Horn DLR) formalism adapted for discrete time and study its computational complexity. We show that the full formalism is NP-hard and identify several maximal tractable subclasses. We also lift the maximality results to obtain hardness results for other families of constraints. Finally, we discuss how the results and techniques presented in this paper can be used for studying even more expressive classes of temporal constraints.
Place, publisher, year, edition, pages
Elsevier , 2013. Vol. 195, 44-62 p.
Temporal reasoning, Discrete time, Computational complexity
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-91019DOI: 10.1016/j.artint.2012.10.001ISI: 000315839600002OAI: oai:DiVA.org:liu-91019DiVA: diva2:615658
Funding Agencies|Swedish Research Council (VR)|621-2009-4431|Swedish National Graduate School in Computer Science (CUGS)||2013-04-192013-04-112013-04-19Bibliographically approved