Treffer: Norms on Semi-Lipschitz Functions: An Approach to Computing Complexity by Partial Functions.

Let T be the recurrence equation in N associated to a given algorithm. If we denote by f the complexity function which is the solution of such a recurrence equation, then f constitutes a total mapping defined recursively that is, at the same time, the limit of a sequence (f<subscript>n</subscript>)<subscript>n</subscript> of partial mappings also defined recursively. In this paper we present a model to compute the complexity represented by f by means of the values that take a certain relativized norm on the sequence (f<subscript>n</subscript>)<subscript>n</subscript> and its initial segments. This is done with the help of a suitable space of semi-Lipschitz functions which is constructed here. [ABSTRACT FROM AUTHOR]

Copyright of AIP Conference Proceedings is the property of American Institute of Physics 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.)