The search functionality is under construction.

The search functionality is under construction.

Reversal complexity has been studied as a fundamental computational resource along with time and space complexity. We revisit it by contrasting with access complexity which we introduce in this study. First, we study the structure of space bounded reversal and access complexity classes. We characterize the complexity classes *L*, *P* and *PSPACE* in terms of space bounded reversal and access complexity classes. We also show that the difference between polynomial space bounded reversal and access complexity is related with the *L* versus *P* problem. Moreover, we introduce a theory of memory access patterns, which is an abstracted structure of the order of memory accesses during a random access computation, and extend the notion of reversal and access complexity for general random access computational models. Then, we give probabilistic analyses of reversal and access complexity for almost all memory access patterns. In particular, we prove that almost all memory access patterns have ω(log *n*) reversal complexity while all languages in *L* are computable within *O*(log *n*) reversal complexity.

- Publication
- IEICE TRANSACTIONS on Information Vol.E91-D No.12 pp.2776-2783

- Publication Date
- 2008/12/01

- Publicized

- Online ISSN
- 1745-1361

- DOI
- 10.1093/ietisy/e91-d.12.2776

- Type of Manuscript
- PAPER

- Category
- Complexity Theory

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Kenya UENO, "Relating L versus P to Reversal versus Access and Their Combinatorial Structures" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 12, pp. 2776-2783, December 2008, doi: 10.1093/ietisy/e91-d.12.2776.

Abstract: Reversal complexity has been studied as a fundamental computational resource along with time and space complexity. We revisit it by contrasting with access complexity which we introduce in this study. First, we study the structure of space bounded reversal and access complexity classes. We characterize the complexity classes *L*, *P* and *PSPACE* in terms of space bounded reversal and access complexity classes. We also show that the difference between polynomial space bounded reversal and access complexity is related with the *L* versus *P* problem. Moreover, we introduce a theory of memory access patterns, which is an abstracted structure of the order of memory accesses during a random access computation, and extend the notion of reversal and access complexity for general random access computational models. Then, we give probabilistic analyses of reversal and access complexity for almost all memory access patterns. In particular, we prove that almost all memory access patterns have ω(log *n*) reversal complexity while all languages in *L* are computable within *O*(log *n*) reversal complexity.

URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.12.2776/_p

Copy

@ARTICLE{e91-d_12_2776,

author={Kenya UENO, },

journal={IEICE TRANSACTIONS on Information},

title={Relating L versus P to Reversal versus Access and Their Combinatorial Structures},

year={2008},

volume={E91-D},

number={12},

pages={2776-2783},

abstract={Reversal complexity has been studied as a fundamental computational resource along with time and space complexity. We revisit it by contrasting with access complexity which we introduce in this study. First, we study the structure of space bounded reversal and access complexity classes. We characterize the complexity classes *L*, *P* and *PSPACE* in terms of space bounded reversal and access complexity classes. We also show that the difference between polynomial space bounded reversal and access complexity is related with the *L* versus *P* problem. Moreover, we introduce a theory of memory access patterns, which is an abstracted structure of the order of memory accesses during a random access computation, and extend the notion of reversal and access complexity for general random access computational models. Then, we give probabilistic analyses of reversal and access complexity for almost all memory access patterns. In particular, we prove that almost all memory access patterns have ω(log *n*) reversal complexity while all languages in *L* are computable within *O*(log *n*) reversal complexity.},

keywords={},

doi={10.1093/ietisy/e91-d.12.2776},

ISSN={1745-1361},

month={December},}

Copy

TY - JOUR

TI - Relating L versus P to Reversal versus Access and Their Combinatorial Structures

T2 - IEICE TRANSACTIONS on Information

SP - 2776

EP - 2783

AU - Kenya UENO

PY - 2008

DO - 10.1093/ietisy/e91-d.12.2776

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E91-D

IS - 12

JA - IEICE TRANSACTIONS on Information

Y1 - December 2008

AB - Reversal complexity has been studied as a fundamental computational resource along with time and space complexity. We revisit it by contrasting with access complexity which we introduce in this study. First, we study the structure of space bounded reversal and access complexity classes. We characterize the complexity classes *L*, *P* and *PSPACE* in terms of space bounded reversal and access complexity classes. We also show that the difference between polynomial space bounded reversal and access complexity is related with the *L* versus *P* problem. Moreover, we introduce a theory of memory access patterns, which is an abstracted structure of the order of memory accesses during a random access computation, and extend the notion of reversal and access complexity for general random access computational models. Then, we give probabilistic analyses of reversal and access complexity for almost all memory access patterns. In particular, we prove that almost all memory access patterns have ω(log *n*) reversal complexity while all languages in *L* are computable within *O*(log *n*) reversal complexity.

ER -