Sequence spaces and asymmetric norms in the theory of computational complexity

In 1995, Schellekens introduced the complexity (quasi-metric) space as a part of the development of a topological foundation for the complexity analysis of algorithms. Recently, Romaguera and Schellekens have obtained several quasi-metric properties of the complexity space which are interesting from a computational point of view, via the analysis of the so-called dual complexity space. Here, we extend the notion of the dual complexity space to the p-dual case, with p > 1, in order to include some other kinds of exponential time algorithms in this study. We show that the dual p-complexity space is isometrically isomorphic to the positive cone of lp endowed with the asymmetric norm ∥ . ∥+p given on lp by ∥ x ∥+p = [Σn^∞=0((xn ∨ 0)^p)]^1/p, where x : = (xn)n∈ω. We also obtain some results on completeness and compactness of these spaces.