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

From International Center for Computational Logic

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

##### Markus KrötzschMarkus Krötzsch

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

```
@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}
}
```