Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1063.68057
García-Raffi, L. M.; Romaguera, S.; Sánchez-Pérez, E. A.
Sequence spaces and asymmetric norms in the theory of computational complexity.
(English)
[J] Math. Comput. Modelling 36, No. 1-2, 1-11 (2002). ISSN 0895-7177

Summary: In 1995, {\it 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, {\it S. Romaguera} and {\it 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.\par 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 $\Vert\cdot\Vert_{+p}$ given on $l_p$ by $\Vert \bold x\Vert_{+p} = [{\Sigma}_{n=0}^{\infty}((x_n \vee 0)^p)]^{1/p}$, where $\bold x := (x_n)_{n\in {\omega}}$. We also obtain some results on completeness and compactness of these spaces.
MSC 2000:
*68Q25 Analysis of algorithms and problem complexity
46A45 Sequence spaces
54E15 Uniform structures and generalizations
54C35 Function spaces (general topology)

Keywords: Dual $p$-complexity space; Asymmetric normed linear space; Bi-Banach space; Strong completeness

Citations: Zbl 0910.68135; Zbl 0941.54028

Cited in: Zbl 1096.46002

Highlights
Master Server