Presentation	2006-04-26 Reducing L versus P to Reversal versus Access Kenya UENO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Reversal complexity has been studied as a fundamental computational resource along with time and space. In this study, we introduce a new complexity resource "access", which is defined as the maximum number of accesses for all space used during computation. We show that many properties for simultaneous space and reversal bounded complexity classes can be applied to simultaneous space and access bounded complexity classes similarly. On the other hand, we show that the difference between reversal and access complexity is intrinsically related with the L versus P problem and many other open questions in complexity theory. We also discuss some results on the reversal versus access problem.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Reversal complexity / the L versus P problem
Paper #	COMP2006-2
Date of Issue

Conference Information
Committee	COMP
Conference Date	2006/4/19(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Reducing L versus P to Reversal versus Access
Sub Title (in English)
Keyword(1)	Reversal complexity
Keyword(2)	the L versus P problem
1st Author's Name	Kenya UENO
1st Author's Affiliation	Department of Computer Science Graduate School of Information Science and Technology the University of Tokyo()
Date	2006-04-26
Paper #	COMP2006-2
Volume (vol)	vol.106
Number (no)	29
Page	pp.pp.-
#Pages	8
Date of Issue