Composition is Almost as Good as S-1-1 (Extended Abstract)
Yves Marcoux · 1989
We establish a polynomial upper bound on the time complexity of 8-1-1 in programming systems with a linear time instance of composition. We also exhibit a family of acceptable such programming systems for which our upper bound is optimal. We deduce several bounds on the time complexity of composition, s-1-1 and var- ious classes of control structures in effective or arbitrary programming systems with a linear or polynomial time in- stance of composition. In particular, we show that any programming system with a polynomial time instance of composition has an exponential time instance of s-1-1. 1 Summary Machtey and Young proved in (MY781 that every effec- tive programming system that has an effective instance (i.e., implementation) of composition necessarily has an effective instance of s-1-1. Riccardi (Ric80, Ric821 noted that the construction of (MY781 did not, in fact, use the effectiveness of the programming system and generalized the validity of the result to arbitrary pro- gramming systems. (Machtey and Young also men- tioned that their construction was applicable to nonef- fective programming systems in (MY81).) Machtey and Young approached the problem from a computability point of view, and were interested in get- ting a simple construction, not an one. Royer (Roy871 noted that their construction was inefficient and could yield a fairly complex instance of s-1-1 even with a rather (e.g., linear time) instance of composition as a starting point. In fact, even with a linear time instance of composition, the construc- tion could yield an instance of s-1-1 requiring double exponential time to compute. Along another line, Royer showed that, in effective programming systems, an instance of s-1-1 guarantees the existence of an almost as efficient in- stance of any control structure with a trivial predicate, a class of control structures that includes most natural ones and, in particular, composition. Royer showed that if the instance of s-1-1 is linear (respectively, poly-