A time-space hierarchy between polynomial time and polynomial space |
| |
Authors: | P. Clote |
| |
Affiliation: | 1. Department of Computer Science, Boston College, 02167, Chestnut Hill, MA, USA
|
| |
Abstract: | In this paper we define a natural time-space hierarchy $$P = F_0 subseteq F_1 subseteq F_2 subseteq cdot cdot cdot subseteq PSPACE$$ between polynomial time and polynomial space and then study the relativizations of this hierarchy, obtaining a relative collapse and a relative proper hierarchy, at each possible level. Some partial results concerning relativized time-space tradeoff are given, together with some open questions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|