*(English)*Zbl 1063.68057

Summary: In 1995, *M. Schellekens* [Proc. MFPS 11, Electronic Notes in Theoretical Computer Science 1, 211–232 (1995; Zbl 0910.68135)] introduced the complexity (quasi-metric) space as a part of the development of a topological foundation for the complexity analysis of algorithms. Recently, *S. Romaguera* and *M. Schellekens* [Topology Appl. 98, 311–322 (1999; Zbl 0941.54028)] 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 ${l}_{p}$ endowed with the asymmetric norm ${\parallel \xb7\parallel}_{+p}$ given on ${l}_{p}$ by ${\parallel \mathbf{x}\parallel}_{+p}={\left[{{\Sigma}}_{n=0}^{\infty}\left({({x}_{n}\vee 0)}^{p}\right)\right]}^{1/p}$, where $\mathbf{x}:={\left({x}_{n}\right)}_{n\in \omega}$. We also obtain some results on completeness and compactness of these spaces.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

46A45 | Sequence spaces |

54E15 | Uniform structures and generalizations |

54C35 | Function spaces (general topology) |