On a relation between uniform coding and problems of the form DTIMEF(F) =? DSPACEF(F)
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-5903Full text not available from this repository.
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|
|Number of Pages:||8|
|Page Range:||pp. 665-672|
Actions (login required)