The search functionality is under construction.
The search functionality is under construction.

Author Search Result

[Author] Akeo ADACHI(1hit)

1-1hit
  • The Time-Space Trade-Off Problem on Relativized Turing Machine

    Akeo ADACHI  Takumi KASAI  

     
    PAPER-Miscellaneous

      Vol:
    E64-E No:3
      Page(s):
    195-202

    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.