P ≠ P
P ≠ P: Why Some Reasoning Problems are More Tractable Than Others
Abstract. Knowledge representation and reasoning leads to a wide range of
computational problems, and it is of great interest to understand the
difficulty of these problems. Today this question is mainly studied using computational
complexity theory and algorithmic complexity analysis. For example,
entailment in propositional Horn logic is P-complete and a specific
algorithm is known that runs in linear time.
Unfortunately, tight algorithmic complexity bounds are rare and
often based on impractical algorithms (e.g., O(n2.373) for transitive closure by matrix multiplication),
whereas computational complexity results abound but are very coarse-grained
(e.g., many P-complete problems cannot be solved in linear time).
In this invited paper, we therefore advocate another approach to gauging the difficulty of a computation: we reformulate computational problems as query answering problems, and then ask how powerful a query language is needed to solve these problems. This reduces reasoning problems to a computational model – query answering – that is supported by many efficient implementations. It is of immediate practical interest to know if a problem can be reduced to query answering in an existing database system. On the theoretical side, it allows us to distinguish problems in a more-fine grained manner than computational complexity without being specific to a particular algorithm. We provide several examples of this approach and discuss its merits and limitations.
Published at RR2014 (Conference paper)
Download PDF (last update: 19 Sep 2014)
Citation details
- Markus Krötzsch. P ≠ P: Why Some Reasoning Problems are More Tractable Than Others. In Roman Kontchakov, Marie-Laure Mugnier, eds.: Proceedings of the 8th International Conference on Web Reasoning and Rule Systems (RR-14), pp. 1–22. SpringerProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2014.
author = {Markus Kr{\"{o}}tzsch},
title = {P${}\neq{}$P: Why Some Reasoning Problems are
More Tractable Than Others},
booktitle = {Proceedings of the 8th Interational Conference
on Web Reasoning and Rule Systems (RR'14)},
editors = {Roman Kontchakov and Marie-Laure Mugnier},
publisher = {Springer},
series = {LNCS},
volume = {8741},
year = {2014},
pages = {1--22},
}
Remarks
This invited paper accompanies a keynote talk at RR 2014.
You can view the presentation in any modern browser. It was prepared using Sozi and Inkscape; many thanks to these projects.
Topics
Query languages, Rule languages, Description logics, Complexity
