The computational complexity of program schemata

摘要

A preordering ⩽1 for comparing the computational complexity is introduced on the class of iterative program schemata. The definition is motivated by showing that several program optimization techniques yield better programs in this sense and by proving the assertion that a schema is better in this sense than another one iff it computes faster for every interpretation and for every assignment of computation times to the single operations. It is shown that a slowdown for all interpretations may be polynomial and is at most polynomial. However, there are program schemata arbitrarily inefficient on a sparse subset of interpretations. Finally, a certain speedup theorem is proved. The results also hold for a less restrictive but less useful preordering. ⩽o that depends only on the lengths of computations.