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. 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 V0)p)]1/p, where x ≔ (xn)nϵω. We also obtain some results on completeness and compactness of these spaces.