Optimization Among Provably Equivalent Programs
Paul R. Young · Journal of the ACM · 1977
The extent to which it is possible, given a program p for computing a function f, to find an optimal program p' which also computes f and is either provably equivalent to p or else provably an optimal program is discussed The methods and problems come chiefly from abstract recurs~on-theoretlc complexity theory, but some of the results may be wewed as directly challenging the intuitive interpretation of earlier results in this area