Computer Science – Computational Complexity
Scientific paper
2006-08-07
Computer Science
Computational Complexity
19 pages, 2 figures
Scientific paper
We study a generalized version of reversal bounded Turing machines where, apart from several tapes on which the number of head reversals is bounded by r(n), there are several further tapes on which head reversals remain unrestricted, but size is bounded by s(n). Recently, such machines were introduced as a formalization of a computation model that restricts random access to external memory and internal memory space. Here, each of the tapes with a restriction on the head reversals corresponds to an external memory device, and the tapes of restricted size model internal memory. We use ST(r(n),s(n),O(1)) to denote the class of all problems that can be solved by deterministic Turing machines that comply to the above resource bounds. Similarly, NST and RST, respectively, are used for the corresponding nondeterministic and randomized classes. While previous papers focused on lower bounds for particular problems, including sorting, the set equality problem, and several query evaluation problems, the present paper addresses the relations between the (R,N)ST-classes and classical complexity classes and investigates the structural complexity of the (R,N)ST-classes. Our main results are (1) a trade-off between internal memory space and external memory head reversals, (2) correspondences between the (R,N)ST-classes and ``classical'' time-bounded, space-bounded, reversal-bounded, and circuit complexity classes, and (3) hierarchies of (R)ST-classes in terms of increasing numbers of head reversals on external memory tapes.
Hernich Andre
Schweikardt Nicole
No associations
LandOfFree
Reversal Complexity Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Reversal Complexity Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reversal Complexity Revisited will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-600831