The Library
On a relation between uniform coding and problems of the form DTIMEF(F) =? DSPACEF(F)
Tools
Tools
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
Full text not available from this repository.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 |
| Date: | August 1998 |
| Volume: | 35 |
| Number: | 8 |
| Number of Pages: | 8 |
| Page Range: | pp. 665-672 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/15405 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
