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 S ROI Q (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.
and compare algorithms and decision problems based on the computational resources they require.
At the centre of research in the theory of computational complexity, or complexity theory, for short, are the complexity classes, i.e. collections of problems that feature the same inherent complexity. Throughout more than half a century of its history, the concept of computational complexity has grown refined and detailed, with many definitions depending on diverse models of computation (deterministic, nondeterministic, and probabilistic machines, alternating computations, Boolean and quantum circuits, interactive protocols, etc.) as well as different measures of complexity (time and space, circuit size and depth, the number of random coin tosses used in a computation, the number of messages exchanged between communication agents, and many more). All of this generates a vast variety of complexity classes related to each other in an intricate manner. The discoveries in the field feature both general theorems, that refer to the properties of whole families of complexity classes, as well as concrete facts about mutual connections between two classes or a class and a problem. what’s known in one unwieldy HTML file”. 1
In a welcome statement to the Complexity Zoo, a website that attempts to collect all the known results in the field with comments and references, its creator Scott Aaronson writes: “I spent a week trying to put AM outside QMA relative to an oracle, only to learn that this followed trivially from two known results. ⟨. . . ⟩ Some theorists seem able to hold in their minds, in one instant, the results of every FOCS, STOC, and Complexity paper ever published. ⟨. . . ⟩ I am not one of those theorists. ⟨. . . ⟩ And so it’s largely for my own benefit that I recorded a chunk of
The Zoo made the life easier for many complexity theorists and many more researchers in other areas of computer science, including the authors of this article. However, it has all the standard drawbacks of old-fashioned plain-text knowledge. First, it does not contain the structural information: if the class P is a subset of the class NP, one can read it in the class description, but the very fact that P ⊆
part of a more complex query. In fact, there is no way to query the Zoo data apart from using textual search. Second, it is not protected from errors or typos: should someone accidentally ⊈ write that P
NP, no one apart from a human user would be able to detect it and report it as a problem. Finally, even though the Zoo can provide the reader with facts and details that help to establish previously unknown relationships between complexity classes, there is no way to do this automatically by inferring new facts from given ones.
We aim at creating a semantic Complexity Zoo, a knowledge graph populated with decision problems and complexity classes, formalising their properties and relations, and equipped with an ontology that provides the semantics and allows the use of off-the-shelf reasoners for query answering, consistency checking and inference tasks. In fact, some of the phenomena of complexity theory, such as infinite hierarchies of complexity classes, actually require ontological axioms even to be described, since they can not be fully represented in the data for obvious reasons. A modest target is building a system capable of answering simple queries and making visualisations, thus facilitating the search of information for researchers and students. An ambitious goal is 1See https://complexityzoo.net/Complexity_Zoo_Introduction. AM and QMA are complexity classes, FOCS is the IEEE Symposium on Foundations of Computer Science, STOC—the ACM Symposium on Theory of Computing, and ‘Complexity’ refers to the Computational Complexity Conference. using it to discover previously unknown, even if simple, facts of the complexity world that follow from the existing results, but that have been overlooked so far.
This paper is the first step on this way. We discuss an approach to ontological modelling of
complexity theory phenomena that is compatible with practical ontological languages and tools,
such as OWL 2 [
Our work uses elements of Semantic Web technologies and addresses issues of foundational
ontologies and the philosophy of mathematics, similar to efforts in formalised mathematics [
In contrast, many ontological investigations into mathematical objects focus on foundational
issues revolving around set theory, categories, and numbers, and explore the classical
philosophical dilemma asking how abstract objects can be so effective and seemingly indispensable in the
systems of modern physics, see [
In Section 2, we introduce, more formally, the notions of complexity theory and highlight the problems that arise when modelling them in an ontology. After that, in Section 3 we axiomatise the domain using a FOWL-inspired approach, that is, writing simpler axioms in OWL 2 DL and the more involved ones in first-order logic. We outline a couple of cases where the power of firstorder logic is yet not enough to capture them. The presentation is wrapped up in Section 4 where we briefly discuss possible ways of further deepening and broadening our ontology, including extending it with a second-order layer to express more subtle details of complexity theory.
The primary objects studied in complexity theory are decision problems and complexity classes.
We start with the definitions. Let f be a mapping {0, 1}∗ → {0, 1}∗ , i.e. a mapping of finite
bit-strings to finite bit-strings. Following the tradition, we will call these bit-strings “words”.
An algorithm computes a function f if on any input word w it outputs f (w). In this article, we
will use the notion of Turing machine, which is the most common model of computation, to
formalise the term “algorithm”, although we plan to include other models to our ontology in the
future. For an algorithm formulated as a Turing machine M, the time complexity is a mapping
TM : N → N, such that on an input word of length n the machine performs at most TM(n) steps
before halting. Space complexity, instead, gives the upper bound on the number of tape cells
used by the machine on an input of length n. The machine itself may be standard deterministic,
with no additional features, or allowed to use extra computational powers such as the ability to
correctly “guess” some useful information (non-deterministic machines), or use randomness to
facilitate its computations (probabilistic machines), etc. Apart from complexity of individual
algorithms, computational problems themselves have a kind of inherent complexity, as observed
by Hartmanis and Stearns [
Traditionally, complexity theorists consider a simpler kind of bit-string functions, whose output
consists of just one bit. Such a function a : {0, 1}∗ → {0, 1} is called a decision problem (or
just a problem), since a can be viewed as a characteristic function of a set, and to compute a
means to “decide” whether the input is in that set. We thus write w ∈ a and w ∈/ a if, respectively,
a(w) = 1 and a(w) = 0. A famous example of a decision problem is SAT: given a Boolean
formula, decide whether it is satisfiable. Complexity classes, or just classes, for brevity, are
defined as sets of decision problems. For example, P is the class of problems decidable by a
deterministic Turing machine in polynomial time. Another related class, NP, contains problems
decidable in polynomial time by a non-deterministic Turing machine. PSPACE is the class of
problems decidable by a deterministic Turing machine using polynomial space. We invite the
reader to consult Arora and Barak [
Problems are members of classes, and classes can contain, or be subsumed by, other classes.
Some set-theoretic relations between them already constitute theorems of complexity theory. For
example, it is an easy consequence of the definitions that SAT ∈ NP and P ⊆ NP, but it requires
some effort to show PSPACE ⊆ EXPTIME, i.e. that every problem decidable in polynomial space
is also decidable in exponential time. Moreover, we know that if SAT ∈ P then P = NP [
elements and the sets are objects of the ontology. 2.1.2. Infinite Constructions Typically, a complexity class is defined with respect to a particular computation model, particular kind of complexity (e.g. time or space) and a bound on that complexity. In this first version of our ontology we will focus on various Turing machines as the models, and time and space complexities. However, for the bounds things are more interesting. Every function g : N → N gives rise to classes DTIME(g) (that of problems decidable in time αg(n) + β , α, β ∈ N, by a deterministic Turing machine), NTIME(g) (the same for nondeterministic Turing machines, which accept if they are able to guess a way to the accepting state), CONTIME(g) (for co-nondeterministic machines, that accept if all their guesses bring them to an accepting state), and ATIME(g) (for alternating machines, that switch between nondeterministic and co-nondeterministic computations), as well as their counterparts for space complexity: DSPACE(g), NSPACE(g), CODSPACE(g) and ASPACE(g). Some of the fundamental theorems make use of this notation. For example, the time hierarchy: if g(n) = o(h(n) · log n), then DTIME(n) ⊊ DTIME(h), or the similar space hierarchy: if g(n) = o(h(n)), then DSPACE(n) ⊊ DSPACE(h). Other examples include the famous Savitch theorem: NSPACE(g) ⊆ DSPACE (︁ g2)︁ , or the standard inclusions DTIME(g) ⊆ DSPACE(g) and a bit more involved DSPACE(g) ⊆ DTIME (2g). However, most of complexity theory is built around “classes” of bounds: constant, logarithmic, polynomial, exponential, double exponential, and so on, with larger complexity classes defined as, e.g., P = ⋃︁k∈N DTIME (︁ nk)︁ . Therefore, we can provide a less fine-grained representation of complexity bounds and the related theory, but we will anyway need to model an infinite sequence of these “classes” of complexity bounds.
depend on their positions in the sequence.
Some of the classes are defined as infinite hierarchies themselves, i.e. sequences of smaller
classes each of which may be of separate theoretical and practical interest. Take, for example,
tahnedpΠol0py⊆nomΠi1pa⊆l hΠier2pa⊆rch. y.,. .PHEa.cIhtcΣokpns(︁ iΠstskp)︁ ofistwaocilnafinssiteofchparoinbsleomfscldasesceids,ablΣe0p b⊆y Σa1pp⊆ olyΣn2po⊆
mi.a.l.time alternating Turing machine that starts in the nondeterministic mode (respectively, the
co-nondeterministic mode) and performs k alternations (see Chandra and Stockmeyer [
2.1.3. Relations of Higher Arity
Arguably, the notions of complexity theory that are the most famous and useful for general
computer science are those of reductions and hardness. A problem a is reducible to a problem b
if there is a function r, called reduction, such that for every word w we have w ∈ a ⇐⇒ r(w) ∈ b
(this definition is due to Karp [
There is a more general notion of reductions between problems, called Turing reducibility (as opposed to Karp reducibility discussed above). Instead of converting an input for a to an input for b and then using the algorithm for b, Turing allows calling the algorithm for b arbitrarily many times in the process of solving a. It is usually assumed that a call to the algorithm for b can be performed within one step of computation. In this case, we say that we are solving a relative to an oracle b, as if we had an access to a powerful being that could instantly decide the problem b whenever requested. This notion gives rise to many more complexity classes: for any class A and any problem b there is a class Ab of problems that are decidable under the restrictions of A given the access to the oracle b. Moreover, for a class B we define AB = ⋃︁b∈B Ab. Many results of complexity theory feature oracles, e.g. the Baker-Gill-Solovay Theorem: there are oracles a and b such that Pa = NPa and P ̸
b = NPb [
2.1.4. Conditional Statements
Complexity theory is rich with questions for which everyone believes in a certain answer but no
one can prove it. This leads to a generous supply of theorems of the form “if α then β ”, where α
and β are certain statements. These theorems state a relationship between two assertions, rather
than prove a particular assertion itself. For example, if NP ⊆ CONP then NP = CONP, P = NP
then EXPTIME = NEXPTIME. If NP ⊆ P/Poly then AM = MA. The first statement is an easy
corollary of the definitions, the second is a good example for the use of the so-called “padding
argument” [
In the next section we address these challenges from the FOWL perspective.
The “real-world” ontology languages, e.g. description logics (DLs) [
Issues of this kind have recently received considerable attention in the literature [
Prob ⊓ Class ⊑ ⊥
As for Challenge 2, the set-theoretic relations can be naturally viewed from a second-order perspective. To stay on the first-order and even description logic level, we simulate the secondorder relations ∈ and ⊆ via dedicated binary relations (or roles, as binary relations are called in description logics) ‘in’ and ‘subset’. In fact, there is not much that we want from these roles. The subset relation is transitive, and the composition of ‘in’ and ‘subset’ gives a ‘in’: (1) (3) (4) (5) We also ensure that these roles respect types of the objects, e.g. the domain of ‘in’ consists of problems and its range—of classes, while for ‘subset’ both the domain and the range are restricted to the objects of type Class: ∃in ⊑ Prob ∃subset ⊑ Class
∃in− ⊑ Class ∃subset− ⊑ Class Simulating equality of classes is less easy. Indeed, we can introduce a role ‘equals’, but the only thing we can say is that it is a sub-relation of both the subset and the superset relations: subset ◦ subset ⊑ subset in ◦ subset ⊑ in (2) equals ⊑ subset equals ⊑ subset− and on the first-order level we can use negation to say that strictSubset(A, B) requires that B is larger than A:
∀x, y . strictSubset(x, y) =⇒ ∃z . in(z, y) ∧ ¬in(z, x) The “full” semantics of equality require reasoning about the intersection of roles ‘subset’ and ‘subset− ’, which is not allowed in S ROI Q. We thus add a first-order axiom: ∀x, y . equals(x, y) ⇐⇒ subset(x, y) ∧ subset(y, x) We can describe other peculiar relations in the same way, such as the strict subset relation. In S ROI Q, we can say that it is a sub-relation of ‘subset’: strictSubset ⊑ subset (6) (7) (8) 3.1.2. Infinite Constructions As we have mentioned in Section 2.1.2, every function N → N defines a complexity bound, but most of the theory is built around “classes” of bounds on time or space: constant, logarithmic, polynomial, exponential, double-exponential, triple-exponential, and so on, where by k-exponential bound we mean the function exp(n, k) defined as exp(n, 1) = 2n and exp(n, k + 1) = 2exp(n,k). Of course, the countable sequence of k-exponentials does not exhaust the world of complexity bounds that are present in the literature, but they are enough to represent most of the results. We come back to this question in Section 4.
We suggest to represent each “class” of complexity bounds by an individual, and subsequent bounds (such as logarithmic and polynomial, or k-exponential and k + 1-exponential, are connected by a functional role ‘nextBound’. Moreover, since we can not explicitly list the whole sequence in the data, we need this role to create an infinite chain. This is done by saying that no object has two or more outgoing or incoming ‘nextBound’ roles, and that an incoming ‘nextBound’ implies the existence of an outgoing one: ⩾ 2 nextBound ⊑ ⊥ ⩾ 2 nextBound− ⊑ ⊥ ∃nextBound− ⊑ ∃nextBound (9) To create the sequence, we only need to declare the existence of an outgoing ‘nextBound’ for the ifrst object: ∃nextBound(Const) (10) And to access any object in the chain, say the exponential bound, it suffices to list all the previous: nextBound(Const, Log) nextBound(Log, Poly) nextBound(Poly, Exp) (11) Complexity classes can now be defined as individuals “attached” to the chain of bounds via specific roles ‘dTime’, ‘nTime’, ‘conTime’, ‘aTime’, and ‘dSpace’, ‘nSpace’, ‘conSpace’, ‘aSpace’ (that are all required to be functional). For example, we assert dTime(P, Poly), and, similarly, conTime(CONP, Poly), dTime(EXPTIME, Exp), dSpace(L, Log), and so on. We express the properties discussed in Section 2.1.2 via role chains. For example, deterministic classes are subsets of the respective non-deterministic classes, and a space class is always contained in the time class with an exponentially higher bound: dTime ◦ nTime− ⊑ subset dSpace ◦ nextBound ◦ dTime− ⊑ subset (12) In particular, the second axiom of (12) ensures that if we go from PSPACE along ‘dSpace’ (arriving at ‘Poly’), then along ‘nextBound’ (to ‘Exp’), and then backwards along ‘dTime’, we will end up at an individual representing a superclass of PSPACE (in this case it will be the class EXPTIME). Technically, by finding the described chain of three roles, we infer subset(PSPACE, EXPTIME). The space and time hierarchies are similar: dSpace ◦ nextBound ◦ dSpace− ⊑ strictSubset dTime ◦ nextBound ◦ dTime− ⊑ strictSubset Savitch theorem is more complicated. In our representation, it means that the role inclusion nSpace ◦ dSpace ⊑ subset holds for all elements of the bounds sequence starting from ‘Poly’. To handle this, we introduce a concept name ‘Savitch’ and assert that, first, it is true for ‘Poly’ and, second, that it spreads along the ‘nextBound’ role, thus covering the whole chain from ‘Poly’ and on:
Savitch ⊑ ∃nextBound.Savitch That is, for any individual labelled with ‘Savitch’ there exists an outgoing ‘nextBound’ to another individual with this label. Since ‘nextBound’ is functional by axioms (9), the label is inferred for the next element in the chain. Finally, we must state that a role chain of nSpace ◦ dSpace− that passes through the label ‘Savitch’ induces a subset relation. To do so, we introduce a new role name ‘nSpaceSavitch’ and say: ⩾ 2 nSpace− ⊑ ⊥
Savitch ⊑ ∃nSpace−Savitch nSpaceSavitch ⊑ nSpace Thus, the existence of ‘Savitch’, e.g., at ‘Poly’, creates an incoming role ‘nSpaceSavitch’, and by design this role has to come along with the existing ‘nSpace’ role. Finally: (13) (14) (15) (16) (17) nSpaceSavitch ◦ dSpace− ⊑ subset We believe that many theorems about hierarchies can be expressed using this approach. This settles Challenge 3.
Indeed, other hierarchies, such as PH, can be modelled in a similar way. We first create an infinite chain of the levels of the hierarchy, where the ith level is represented by an object ℓi, and the objects ℓk and ℓk+1 are connected by the ‘nextLevelPH’ role, that is functional in both directions and has the same properties as ‘nextBound’ in (9). We start the chain at the level ℓ0 and attach the class P to it by two parallel roles: sigmap(P, ℓ0) and pip(P, ℓ0). For the higher levels, these two roles are used to connect to ℓk the two respective classes, Σk and Πkp. It is not hard to p express the subset relationships between these classes in the same fashion as we did before.
There are two more tricky issues about PH. The first is that the whole hierarchy is contained in PSPACE. This is easy to say in FOL, but we can also do it in S ROI Q. For that we introduce a role ‘higherLevelPH’, define it as the transitive closure of ‘ nextLevelPH’, and use it to get from any level of the hierarchy back to P, and then to PSPACE, via a suitable chain of roles: nextLevelPH ⊑ higherLevelPH
nextLevelPH ◦ higherLevelPH ⊑ higherLevelPH sigmap ◦ higherLevel−PH ◦ sigmap− ◦ dTime ◦ dSpace− ⊑ subset (18) (19) Read (19) as follows: from a class Σkp we step, via ‘sigmap’, to ℓk; from there we get down to ℓ0, where we by ‘sigmap− ’ get to P; and from P we get to PSPACE via dTime ◦ dSpace− , passing through the object ‘Poly’ in the chain of bounds.
The second issue is exactly Challenge 4: to define the class PH itself as a “limit” point of the sequence. In FOWL, we are able to give only a partial solution to this problem. Indeed, like with PSPACE above, we can say that Σkp ⊆ PH for all k. However, it remains to state that PH is subsumed by the union of Σkp, i.e. that if ‘in(a, PH)’ is true, then there exists Σkp in the chain that contains a. We leave it as a question of further development and briefly discuss it again in Section 4. 3.1.3. Relations of Higher Arity We now settle Challenge 5. We need first-order logic to work with relations of arity 3, such as reachability and hardness. On the other hand, most of reductions in the “textbook” complexity theory are polynomial time or logarithmic space reductions. Therefore, it makes sense to provide S ROI Q variants for these types of reductions.
We introduce roles isReducibleL and isReducibleP, and, similarly, isHardL and isHardP for hardness relations with respect to these complexity bounds. We can express some of their properties in S ROI Q, e.g. both reducibility relations are transitive, being hard for a class results in being hard for any of its subclasses, and if a hard problem is reducible to another one, than that one is also hard. Thus, for F ∈ {L, P}: isReducibleF ◦ isReducibleF ⊑ isReducibleF isHardF ◦ subset− ⊑ isHardF (isReducibleF )− ◦ isHardF ⊑ isHardF Also, as one can expect, every logspace reduction can be computed in polynomial time: isReducibleL ⊑ isReducibleP isHardL ⊑ isHardP These roles can be connected back to their first-order originals. For example, for logspace reducibility it is done as follows:
∀x, y . isReducibleL(x, y) ⇐⇒ isReducible(x, y, L) A class Ab is defined via two objects, A and b. This can be represented by a pair of roles: ‘hasBase’ and ‘hasPower’. For example NP = PSAT, therefore we write hasBase(A, P), hasPower(A, SAT), equals(NP, A). In this setting, stating Ladner’s Theorem is done via ABox assertions using special objects that are mentioned in the theorem, i.e. the Ladner’s oracle l and the classes Pl, and NPl, for which the following is stated: hasBase(Pl, P), hasPower(Pl, l), hasBase(NPl, NP), hasPower(NPl, l), notEquals(Pl, NPl). (20) (21) (22) (23) (24) 3.1.4. Conditional Statements Most of the conditional statements can be treated as implications between ABox assertions, that are easy to reason about within Boolean logic, as in equals(P, NP) =⇒ equals(EXPTIME, NEXPTIME) (25) In cases that assert existence of an object if a certain condition is true, we can introduce such an object as a “certifier” for the result: ¬equals(P, NP) =⇒ in(certifier , NP) ∧ ¬isHardPoly(certifier , NP) (26)
For a more distant future, we foresee four ways of enhancing the ontology: • Broadening. There are many more notions and related to them phenomena of complexity theory that we are not addressing here. From diverse models of computation (such as finite automata, Boolean circuits, probabilistic and quantum machines) to different approaches to define complexity classes (such as descriptive complexity) to connections with algebra and number theory: there is a lot of human knowledge on the subject to systematise in a machine-readable way. • Deepening. As we have mentioned, our current approach focuses on the ‘core knowledge’ of complexity theory, i.e. the knowledge one usually acquires in an introductory undergraduate course. However, many more subtle details are swept under the carpet with this approach. For example, we work only with “large” classes like P and PSPACE, and thus do not mention important facts such as P ̸= DSPACE(n). Indeed, P and PSPACE, are themselves hierarchies of classes DTIME(nk) and DSPACE(nk). The expressiveness of FOWL is enough to add these and other details. • Increasing complexity. Currently, we were only able to provide a partial solution to Challenge 4. Apart from the polynomial hierarchy, defining ‘limits’ of chains is important for other aspects of complexity theory. For example, our chain of bounds (Const, Log, Poly, Exp, 2Exp, 3Exp, ...) has, in fact, a limit, the tower function t(n) defined by t(0) = 1 and t(n + 1) = 2t(n). Functions that require time t(n) to be computed are called non-elementary [27]. But this is not the end: there are Ackermann-hard computational problems [28] that have time complexity higher than the tower function, and further on [29, 30]. Representing and axiomatising these phenomena will, we believe, require more expressive formalisms, such as second-order logic. • Adding metadata. In addition to representing the complexity theoretic results, it will be useful to provide meta-information, such as references to papers where a certain fact was (first) demonstrated, the proof techniques used, etc.
A separate research direction is providing a strong ontological and knowledge-engineering basis for our ontology. This would include defining basic notions of computer science, such as algorithms, models of computation, complexity measures and their relationships, in one or several mid-level ontologies, and further connecting them to a top-level ontology. [27] L. J. Stockmeyer, The complexity of decision problems in automata theory and logic, Ph.D. thesis, Massachusetts Institute of Technology, 1974. URL: https://api.semanticscholar.org/ CorpusID:62162426. [28] W. Czerwinski, L. Orlikowski, Reachability in vector addition systems is ackermanncomplete, in: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 1229–1240. doi:10.1109/FOCS52979.2021.00120. [29] H. Rogers, Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, USA, 1987. URL: https://mitpress.mit.edu/9780262680523/ theory-of-recursive-functions-and-effective-computability/. [30] P. G. Hinman, Classical recursion theory. the theory of functions and sets of natural numbers., Journal of Symbolic Logic 55 (1990). doi:10.2307/2274492.