1-1hit |
The "relativized Turing machines" are introduced as media executing program schemas. On these machines, it is proved that, for any a, 0a1, there exists an O(na) space and O(n2-a log n) time bounded program schema to sort n elements, and any O(na) space bounded schema to sort n elements requires more than O(n2-a) time. Furthermore, it is shown that there exists a problem which causes a large scale time-space trade off. That is, we show the existence of a problem Q such that there is an O(n2) space and polynomial time bounded schema to compute Q, and there is an O(n log n) space bounded schema to compute Q, and further, any S(n) space bounded schema requires more than exponential time if S(n)n2.