The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “On the structure of the dual complexity space: The general case.”

Computing complexity distances between algorithms

Salvador Romaguera, Enrique A. Sánchez-Pérez, Oscar Valero (2003)

Kybernetika

Similarity:

We introduce a new (extended) quasi-metric on the so-called dual p-complexity space, which is suitable to give a quantitative measure of the improvement in complexity obtained when a complexity function is replaced by a more efficient complexity function on all inputs, and show that this distance function has the advantage of possessing rich topological and quasi-metric properties. In particular, its induced topology is Hausdorff and completely regular. Our approach is applied to the...

On half-completion and bicompletion of quasi-metric spaces

Elena Alemany, Salvador Romaguera (1996)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We characterize the quasi-metric spaces which have a quasi-metric half-completion and deduce that each paracompact co-stable quasi-metric space having a quasi-metric half-completion is metrizable. We also characterize the quasi-metric spaces whose bicompletion is quasi-metric and it is shown that the bicompletion of each quasi-metric compatible with a quasi-metrizable space X is quasi-metric if and only if X is finite.