Ontological Modelling Principles for Computational Complexity

The field of computational complexity theory is a core theoretical subject in computer science with significant impact also for real-world applications. Although a plethora of individual results are known, a systematic conceptual organisation of this knowledge is still lacking. We propose a modelling approach for creating an ontologically well-founded knowledge base for the theory of computational complexity that will enable storing, querying and reasoning over the vast knowledge of algorithmic problems, complexity classes and their relationships. We determine the core concepts and relations of complexity theory and model them on two levels of approximation: a lightweight version based on the decidable description logic S R O I Q (the underlying formalism of the ontology language OWL 2 DL) and a further extended version based on first-order logic.