Kybernetika

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 measurement of distances between infinite words over the decimal alphabet and some advantages of our computations with respect to the ones that provide the classical Baire metric are discussed.

Finally, we show that the application of fixed point methods to the complexity analysis of Divide and Conquer algorithms, presented by M. Schellekens (Electronic Notes in Theoret. Comput. Sci.1(1995)), can be also given from our approach.