The Time-Space Trade-Off Problem on Relativized Turing Machine

Akeo ADACHI; Takumi KASAI

The Time-Space Trade-Off Problem on Relativized Turing Machine

Akeo ADACHI, Takumi KASAI

Full Text Views

0

Cite this

Summary :

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(n^a) space and O(n^2-a log n) time bounded program schema to sort n elements, and any O(n^a) space bounded schema to sort n elements requires more than O(n^2-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(n²) 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)n².

Publication: IEICE TRANSACTIONS on transactions Vol.E64-E No.3 pp.195-202

Publication Date: 1981/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Miscellaneous

Authors

Akeo ADACHI
Takumi KASAI

Keyword

Cite this

Copy

Akeo ADACHI, Takumi KASAI, "The Time-Space Trade-Off Problem on Relativized Turing Machine" in IEICE TRANSACTIONS on transactions, vol. E64-E, no. 3, pp. 195-202, March 1981, doi: .
Abstract: 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(n^a) space and O(n^2-a log n) time bounded program schema to sort n elements, and any O(n^a) space bounded schema to sort n elements requires more than O(n^2-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(n²) 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)n².
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e64-e_3_195/_p

Copy

@ARTICLE{e64-e_3_195,
author={Akeo ADACHI, Takumi KASAI, },
journal={IEICE TRANSACTIONS on transactions},
title={The Time-Space Trade-Off Problem on Relativized Turing Machine},
year={1981},
volume={E64-E},
number={3},
pages={195-202},
abstract={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(n^a) space and O(n^2-a log n) time bounded program schema to sort n elements, and any O(n^a) space bounded schema to sort n elements requires more than O(n^2-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(n²) 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)n².},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - The Time-Space Trade-Off Problem on Relativized Turing Machine
T2 - IEICE TRANSACTIONS on transactions
SP - 195
EP - 202
AU - Akeo ADACHI
AU - Takumi KASAI
PY - 1981
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E64-E
IS - 3
JA - IEICE TRANSACTIONS on transactions
Y1 - March 1981
AB - 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(n^a) space and O(n^2-a log n) time bounded program schema to sort n elements, and any O(n^a) space bounded schema to sort n elements requires more than O(n^2-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(n²) 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)n².
ER -