首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号