## 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

### Keywords:

Smyth-completeness; quasi-uniform space; complexity space
Full Text: