The Library
On a relation between uniform coding and problems of the form DTIMEF(F) =? DSPACEF(F)
Tools
UNSPECIFIED (1998) On a relation between uniform coding and problems of the form DTIMEF(F) =? DSPACEF(F). ACTA INFORMATICA, 35 (8). pp. 665-672. ISSN 0001-5903.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
If uniform coding (Godelization) of potentially infinite sequences of numbers can be performed in PSPACEF, then PSPACE = EXPTIME not equal EXPSPACE = 2-EXPTIME, and, for all p, we have p-EXPSPACE = P + 1-EXPTIME; if it can be performed in LINSPACEF, we also have LINSPACE = DTIME(2(cx)); the proof fails, when relativized to oracle-TM's. A by-product of this research is that PTIMEF is not closed under number-theoretic, limited, course-of-values recursion.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | ACTA INFORMATICA | ||||
Publisher: | SPRINGER VERLAG | ||||
ISSN: | 0001-5903 | ||||
Official Date: | August 1998 | ||||
Dates: |
|
||||
Volume: | 35 | ||||
Number: | 8 | ||||
Number of Pages: | 8 | ||||
Page Range: | pp. 665-672 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |