System T, call-by-value and the minimum problem

✍ Scribed by Loïc Colson; Daniel Fredholm

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 855 KB
• Volume: 206
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00011-5

✦ Synopsis

It is shown that for Giidels system T, evaluated call-by-value, if an algorithm computes a non-trivial binary function (where trivial means constant or projection plus constant), then the time-complexity is at least linear in one of the inputs. This is in contrast to the call-by-name case. As a corollary, it follows that there is no algorithm in this setting which computes the minimumfunction in time-complexity O(min).