×

Quasi-metric properties of complexity spaces. (English) Zbl 0941.54028

Recall that a quasi-uniform space \((X,{\mathcal U})\) is bicomplete iff the uniform space \((X,{\mathcal U}^s)\) is complete, where \({\mathcal U}^s:={\mathcal U}\vee{\mathcal U}^{-1}\); it is Smyth-completeable iff every left K-Cauchy filter on \((X,{\mathcal U})\) is a Cauchy filter on \((X,{\mathcal U}^s)\). The complexity space \(C:= \{f: \omega\to (0,+\infty]\); \(\sum (2^{-n} f(n)^{-1}< \infty\}\) with the quasi metric \(\rho(f,g):= \sum 2^{-n} \max\{ g(n)^{-1}- f(n)^{-1},0\}\) and its dual space \(C^*:= \{f:\to \mathbb{R}\); \(\sum 2^{-n} f(n)<+\infty\}\) with the quasi-metric \(\rho^*(f,g):= \sum 2^{-n} \max\{g(n)- f(n),0\}\) are discussed in this paper. It is shown that the quasi-uniform space associated with \((C^*, \rho^*)\) is Smyth-complete and consequently is a Baire space. For a closed \({\mathcal F}\subseteq C^*\) and for \(m\in C^*\) the space \({\mathcal F}_m:= \{f\in{\mathcal F}\); \(m\) is an upper bound for \(f\}\) with metric \(\rho^s(f,g):= \rho^*(f,g)+ \rho^*(g,f)\) turns out to be a compact metric space. The paper is nicely written, but the reader (like the reviewer) would have appreciated a little more self-containedness. The computational significance of the results are far from being clear and might have been pointed out in greater detail by the authors.

MSC:

54E15 Uniform structures and generalizations
54C30 Real-valued functions in general topology
54E35 Metric spaces, metrizability
54C35 Function spaces in general topology
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI