P ≠ P: Why Some Reasoning Problems Are More Tractable Than Others

Markus KrötzschMarkus Krötzsch

ISBN: 978-3-319-11113-1
ISSN: 0302-9743
Download
DOI Link

Markus Krötzsch
P ≠ P: Why Some Reasoning Problems Are More Tractable Than Others
Proc. 8th International Conference on Web Reasoning and Rule Systems (RR'14), volume 8741 of LNCS, 1-22, September 2014. Springer

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: This invited paper accompanies a keynote talk at RR 2014.
Projekt:Project: DIAMOND
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-11113-1_1.

@inproceedings{K2014,
  author    = {Markus Kr{\"{o}}tzsch},
  title     = {P {$\neq$} P: Why Some Reasoning Problems Are More Tractable Than
               Others},
  booktitle = {Proc. 8th International Conference on Web Reasoning and Rule
               Systems (RR'14)},
  series    = {LNCS},
  volume    = {8741},
  publisher = {Springer},
  year      = {2014},
  month     = {September},
  pages     = {1-22},
  doi       = {10.1007/978-3-319-11113-1_1}
}