Some Hierarchies of Relativized Time-Bounded Complexity Classes
Hisao Tanaka, Masa-aki Izumi, Nobuyuki Takahashi · Publications of the Research Institute for Mathematical Sciences · 1985
Some results on relativized time-bounded complexity classes are presented.There can be many kinds of hierarchies of complexity subclasses of relativized NP.For brevity, let P(A, k) \NP(A, k)} be the relativized complexity class DTIME^(/i*) [resp.NTIME^/i*)] with respect to oracle set A. (For k=l, replace n k by 2ri).Then for example: 1).There is an oracle set A such that for all k>Q P(A, k) is properly contained in NP(>4, k) and NP(/4, k) is properly contained in P(A, k+l).2) For each &>0, there is an oracle set D (depending on k) such that for any i , z)but for all j>k P(D,j)=NP(D,j).Besides, we show a theorem which is a higher level analog to a theorem of Book, Wilson and Mei-Rui [3],