Provable conditions in computational complexity theory
Daryel Sachse-Åkerlind · Bulletin of the Australian Mathematical Society · 1985
Computational complexity measures and indexings of algorithms are considered within a formal axiomatic system 5 .5 is meant to mimic the formal system within which the study of computational complexity is (implicitly) carried out -so, for example, S can tie a conventional axiomatization of set theory.The main thrust of the thesis is that for many natural questions about the complexity of algorithms, what can be formally proved falls unpleasantly short of what is actually true.We consider abstract Blum measures over indexings of the partial recursive functions.Our results fall into three categories.First we consider complexity questions involving some arbitrary given partial recursive function / .Associated with / will be an algorithm used to define f .Before any other algorithm can be admitted as a means of calculating / , i t must be proved equivalent to our defining algorithm for / .The requirement of being provably equivalent defines an equivalence relation on the set of all algorithms.We call the equivalence classes provable equivalence classes.We show that for natural complexity questions about / , what can be proved about f depends on the provable equivalence class to which the defining algorithm for / belongs.