Displaying similar documents to “Cartesian closed hull for (quasi-)metric spaces (revisited)”

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