Abstract
Asymmetric Norms and the Dual Complexity Spaces
One of the recent advances in Computer Science was due to the possibility of
establishing a mathematical model that account the distance between algorithms
and programs when they are analyzed in terms of their computational complexity
(complexity distance), where computational complexity is interpreted in terms of
running time, for example.
In the last decade, several authors have done a big e_ort in obtaining a robust
mathematical theory, which was a useful tool that played, in this context, a similar
role that normed linear spaces have played in di_erent scienti_c areas.
In the context of Computational Complexity, it is shown that Asymmetric Normed
Linear Spaces constitute a very satisfactory model. This thesis is focused in the
study of the properties of these spaces, similarly to the classical properties that
are studied in the case of normed linear spaces. Thus, we have studied separation
properties of asymmetric normed linear spaces, obtaining in particular a characterization
of Hausdor_ness; we have obtained a satisfactory theory of bicompletion
for these spaces; we have analyzed compactness on _nite dimensional asymmetric
normed linear spaces; we have studied conditions under which an asymmetric
norm de_ned on an algebraically closed subset of a linear space can be extended
to the whole space and we have analyzed the structure of the dual space and the
weak topologies associated to it. Finally, we have applied our theory to Computer
Science, speci_cally to the so-called Dual Complexity Spaces.