Sequence spaces and asymmetric norms in the theory of computational complexity
Saved in:
| Title: | Sequence spaces and asymmetric norms in the theory of computational complexity |
|---|---|
| Authors: | García-Raffi, L.M.1, Romaguera, S., Sánchez-Pérez, E.A.1 |
| Source: | Mathematical & Computer Modelling. Jul2002, Vol. 36 Issue 1/2, p1. 11p. |
| Subjects: | Computational complexity, Sequence spaces |
| Abstract: | 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 &z.sfnc;.&z.sfnc;+p given on lp by &z.sfnc;x&z.sfnc;+p = [∑n=0∞((xn V0)p)]1/p, where x ≔ (xn)n∊ω. We also obtain some results on completeness and compactness of these spaces. [Copyright &y& Elsevier] |
| Copyright of Mathematical & Computer Modelling is the property of Pergamon Press - An Imprint of Elsevier Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 7916821 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Sequence spaces and asymmetric norms in the theory of computational complexity – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22García-Raffi%2C+L%2EM%2E%22">García-Raffi, L.M.</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Romaguera%2C+S%2E%22">Romaguera, S.</searchLink><br /><searchLink fieldCode="AR" term="%22Sánchez-Pérez%2C+E%2EA%2E%22">Sánchez-Pérez, E.A.</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Mathematical+%26+Computer+Modelling%22">Mathematical & Computer Modelling</searchLink>. Jul2002, Vol. 36 Issue 1/2, p1. 11p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Sequence+spaces%22">Sequence spaces</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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 &z.sfnc;.&z.sfnc;+p given on lp by &z.sfnc;<B>x</B>&z.sfnc;+p = [∑n=0∞((xn V0)p)]1/p, where <B>x</B> ≔ (xn)n∊ω. We also obtain some results on completeness and compactness of these spaces. [Copyright &y& Elsevier] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Mathematical & Computer Modelling is the property of Pergamon Press - An Imprint of Elsevier Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=7916821 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/S0895-7177(02)00100-0 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 11 StartPage: 1 Subjects: – SubjectFull: Computational complexity Type: general – SubjectFull: Sequence spaces Type: general Titles: – TitleFull: Sequence spaces and asymmetric norms in the theory of computational complexity Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: García-Raffi, L.M. – PersonEntity: Name: NameFull: Romaguera, S. – PersonEntity: Name: NameFull: Sánchez-Pérez, E.A. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: Jul2002 Type: published Y: 2002 Identifiers: – Type: issn-print Value: 08957177 Numbering: – Type: volume Value: 36 – Type: issue Value: 1/2 Titles: – TitleFull: Mathematical & Computer Modelling Type: main |
| ResultId | 1 |
