Complexity spaces as quantitative domains of computation (Q536037)

Complexity spaces offer a domain-theoretic platform to talk about issues of computational complexity by exporting order-theoretic and topological tools. This paper in particular addresses the question of the extent complexity spaces can be incorporated as a quantitative domain. Two classes of complexity spaces are given particular treatment here: (i) pointed complexity spaces, and (ii) the general complexity space. Pointed complexity spaces are natural as most comparison-based sorting algorithms already satisfy the well-known \(\Omega(n \log n)\) lower bound. The important starting point is to pass to defining a quasi-metric space, and to define an order-relation on the complexity space. This initial approach fails to yield a domain structure since continuity fails, though the underlying order is a dcpo. The nice point here is that once we restrict ourselves to the pointed complexity space with a certain lower bound \(f_0\), everything falls in place. Importantly, the pointed complexity space is an \(\omega\)-continuous domain for which the quasi-metric induces the Scott topology. In the perspective of quantitative domain theory, the structure of pointed complexity space has the desirable property that it is a quantifiable domain in the sense of M. Schellekens and a quantitative domain in the sense of (the late) P. Waszkiewicz. Readers who are seeking the connection between the theory of complexity and domain theory should find this paper informative and elegant to read.