An Effective Procedure for Speeding Up Algorithms

Title: An Effective Procedure for Speeding Up Algorithms

Abstract: This research aims to develop an effective procedure for speeding up algorithms, particularly for formally defined problems. The main idea is to enumerate all programs that are provably equivalent to the original problem by enumerating all proofs. This approach allows for the construction of the fastest algorithm within a factor of 5 for these problems. The algorithm can be interpreted as a generalization and improvement of Levin search, which is within a multiplicative constant the fastest algorithm for inverting functions. The research shows that the fastest program that computes a certain function is also one of the shortest programs provably computing this function. To quantify this statement, the research defines two new natural measures for the complexity of a function.

Results: The research presents Theorem 1, which states that for a given algorithm computing p*(x) from x, or more generally, a specification of a function, and any algorithm computing provably the same function with computation time provably bounded by the function tp(x), the algorithm Mp*(x) constructed in Section 3 computes p*(x) in time:

   time Mp*(x) ≤ 5 · tp(x) + dp · time tp(x) + cp

where cp and dp depend on p but not on x. The research also discusses the implications of this result, including the fact that the fastest program that computes a certain function is also one of the shortest programs provably computing this function.

Implications: The research's findings have significant implications for the field of computer science. The developed procedure can be applied to a wide range of problems, not just inversion problems. The results show that there is no large multiplicative factor in the computation time, which makes the procedure more practical. However, the research also highlights the large additive constant cp, which may limit the practical applicability of the Mp*(x) algorithm.

Link to Article: https://arxiv.org/abs/0102018v1 Authors: arXiv ID: 0102018v1