Some properties of exponential time complexity classes
Bin Fu, Li Hongzhou, Yong Zhong · 2003
The authors separate NE from P/sub x/ (NP), where x=n/sup 0(1)/-T. The class EXP-low(1) is introduced and applied in the investigations of stable properties for both EXP and NEXP hard sets. A set A is in EXP-low(1)(EXP-low resp.) if EXP/sup A(1)/=EXP(EXP/sup A/=EXP). The authors separate EXP-low(1) from EXP-low by constructing a set A such that EXP/sup A(1)/=EXP and EXP/sup A/=EXP/sup EXP/.>