A POSITIVE RELATIVIZATION OF POLYNOMIAL-TIME VERSUS POLYLOG SPACE

Authors
GAVALDA R
Citation
R. Gavalda, A POSITIVE RELATIVIZATION OF POLYNOMIAL-TIME VERSUS POLYLOG SPACE, Information processing letters, 46(3), 1993, pp. 119-123
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
46
Issue
3
Year of publication
1993
Pages
119 - 123
Database
ISI
SICI code
0020-0190(1993)46:3<119:APROPV>2.0.ZU;2-N
Abstract
Can every problem in P be solved in polylogarithmic space? We show tha t this question is equivalent to whether the class E is included in th e class PSPACE relative to any oracle, for a restricted type of oracle machine. We give a similar characterization for the problem of whethe r Polylog space is included in P. The proofs are based on translation arguments different from those used in the literature.