Relationship Among Some Relativized Time Complexity Classes

概要

論文の詳細を見る
Although we know that NP and DEXT(=∪__<c>0> DTlME(2^<cn>)) are different, we do not know the precise inclusion relation between them. To obtain a better understanding of the relation between these two classes, we introduce the class ΠΕ_k of the languages acceptable by 2^<lin>-time-bounded Turing machines making at most n^k nondeterministic moves on inputs of length n. These classes constitute a hierarchy DEXT=ΠΕ_1⊆ΠΕ_2⊆ΠΕ_3⊆...⊆NEXT(=∪__<c>0> NTIME(2^<cn>)) between DEXT and NEXT, and we are interested in the relation between NP and these ΠΕ_k. We show the following results on the relativized classes NP(X) and ΠΕ_k(X) with respect to oracle sets X. (1)There is an oracle set A such that NP(A)-ΠΕ_k(A)≠φ and ΠΕ_k(A)-NP(A)≠φ for every k≥1. (2)For each k≥2, there is an oracle set B_k such that NP(B_k)-ΠΕ_<k-1>(B_k)≠φ but NP(B_k)⊊ΠΕ_k(B_k). The precise relation between NEXT and EXP(=∪__<c>0> DTIME(2^<n'>)) is also unknown. For the relativization of these classes, we show that (3)There is an oracle set C such that NEXT(C)-EXP(C)≠φ and EXP(C)-NEXT(C)≠φ.
一般社団法人情報処理学会の論文
1986-03-31