TY - JOUR
T1 - A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
AU - Moriya, Etsuro
AU - Iwata, Shigeki
AU - Kasai, Takumi
PY - 1986
Y1 - 1986
N2 - Simultaneous resource bounded complexity classes for nondeterministic single worktape off-line Turing machines are considered such as time-space bounded classes, denoted by NTISP1(T, S), reversal-space bounded classes, denoted by NRESP1(R, S), and time-reversal bounded classes, denoted by NTIRE1(T, R). It is shown that NRESP1(R(n), S(n)) contains NTISP1(S(n), R(n)) and is contained in NTISP1(R(n) S(n)n2 log n, R(n) log n). The following corollaries follow: (1) the affirmative solution to the nondeterministic single worktape version of the NC = ? SC problem, NTIRE1(poly, polylog) = NTISP1(poly, polylog), and (2) a reversal-space trade-off, NRESP1(polylog, poly) = NRESP1(poly, polylog).
AB - Simultaneous resource bounded complexity classes for nondeterministic single worktape off-line Turing machines are considered such as time-space bounded classes, denoted by NTISP1(T, S), reversal-space bounded classes, denoted by NRESP1(R, S), and time-reversal bounded classes, denoted by NTIRE1(T, R). It is shown that NRESP1(R(n), S(n)) contains NTISP1(S(n), R(n)) and is contained in NTISP1(R(n) S(n)n2 log n, R(n) log n). The following corollaries follow: (1) the affirmative solution to the nondeterministic single worktape version of the NC = ? SC problem, NTIRE1(poly, polylog) = NTISP1(poly, polylog), and (2) a reversal-space trade-off, NRESP1(polylog, poly) = NRESP1(poly, polylog).
UR - http://www.scopus.com/inward/record.url?scp=0022761996&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022761996&partnerID=8YFLogxK
U2 - 10.1016/S0019-9958(86)80003-1
DO - 10.1016/S0019-9958(86)80003-1
M3 - Article
AN - SCOPUS:0022761996
SN - 0019-9958
VL - 70
SP - 179
EP - 185
JO - Information and control
JF - Information and control
IS - 2-3
ER -