Abstract
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, the conceptual organisation of this knowledge is still lacking. We propose the first steps towards creating an ontologically well-founded knowledge base for the theory of computational complexity that will allow storing, querying and reasoning over the vast knowledge of algorithmic problems, complexity classes and their relationships, developed by human experts. We determine the core concepts and relations of complexity theory and model them on two levels of approximation: the description logic SROIQ (a.k.a. OWL 2 DL) and first-order logic. Finally, we point out a number of phenomena that require more expressive formalisms beyond the first-order paradigm.