多项式时间、指数时间复杂性类关于禁性的一个结果

本文证明:存在信息源集 A,使得 NP(A)中含有 P(A)——禁集,但 NEXPTIME(A)-=EXPTIME(A),从而说明不能用文[1]中方法解决“是否有 NP 含有 P——禁集的正相对化结果”这个问题。