[Back]

T. Eiter:
"A Hitchhiker's Tour Through Computational Complexity in Knowledge Representation and Reasoning";
Keynote Lecture: KR 2020 - 17th International Conference on Principles of Knowledge Representation and Reasoning, Rhodos, Griechenland; 2020-09-12 - 2020-09-18.

The vision of artificial intelligence with human-level capabilities of reasoning has inspired and motivated generations of researchers, starting with John McCarthy's seminal work to develop numerous formalisms and approaches towards making it a reality. Many of these formalisms are rooted in formal logic or mathematical approaches to deal with world models at a symbolic level, allowing to take aspects such as incomplete information, uncertainty, or inconsistency into account. The undecidability of first-order logic, which often served as the basis, has spurred the search for decidable fragments in order to facilitate effective reasoning. However, mere decidability turned out to be insufficient in practice, and tractability as a paradigm for efficient solvability was fostered.

Structural complexity theory, which is concerned with problem solving under resource constraints and describing its inherent difficulty, turned out to be a valuable tool in the design of formalisms and for the analysis of reasoning tasks in them. In fact the rich landscape of complexity classes with various models of computation and resource settings, has facilitated a fine-grained analysis beyond a black-white characterization of being tractable or intractable, where NP-hardness was perceived as a kiss of death for problems in practice. In turn, problems in Knowledge Representation and Reasoning (KRR) have vitalized complexity classes that were considered to be more of academic interest, and led to the development of new notions and techniques.

In this talk, we shall address the role of computational complexity in KRR. We shall consider why complexity matters and what conclusions can be drawn from complexity results beyond mere quantitative (in terms of resource consumption) results. With a focus on selected examples, we shall review some highlights and influential results, consider developments and recent trends, and perhaps risk a glimpse into the future: while regarded almost indispensable today, may the need for complexity considerations vanish?