Complexity spaces as quantitative domains of computation (Q536037): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2081459260 / rank | |||
Normal rank |
Revision as of 01:44, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity spaces as quantitative domains of computation |
scientific article |
Statements
Complexity spaces as quantitative domains of computation (English)
0 references
16 May 2011
0 references
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.
0 references
complexity space
0 references
pointed complexity space
0 references
continuous domain
0 references
Scot topology
0 references
quantitative domain
0 references
computational complexity
0 references