Treffer: A positive relativization of polynomial time versus polylog space
Title:
A positive relativization of polynomial time versus polylog space
Authors:
Source:
Information processing letters. 46(3):119-123
Publisher Information:
Amsterdam: Elsevier Science, 1993.
Publication Year:
1993
Physical Description:
print, 9 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Classe complexité, Complexity class, Clase complejidad, Complexité calcul, Computing complexity, Complejidad cálculo, Relativisation, Relativization
Document Type:
Fachzeitschrift
Article
File Description:
text
Language:
English
Author Affiliations:
Univ. politèc. Catalunya, dep. software, 08028 Barcelona, Spain
ISSN:
0020-0190
Rights:
Copyright 1993 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.4902512
Database:
PASCAL Archive
Weitere Informationen
Can every problem in P be solved in polylogarithmic space? We show that this question is equivalent to whether the class E is included in the class PSPACE relative to any oracle, for a restricted type of oracle machine. We give a similar characterization for the problem of whether polylog space is included in P. The proofs are based on translation arguments different from those used in the literature.