关于相对化的计算复杂性类的研究(摘要)

设P~A 及NP~A 分别表示被多项式时间有界的确定性与非确定性的带oracleA 的图灵机所接受的语言类;E~A 及NE~A 分别表示被指数时间有界的确定性与非确定性的带oracleA的图灵机所接受的语言类.不失一般性,设图灵机的带上字母表为{0,1}.本文所讨论的语言(集合)及字分别指{0,1}~*的子集及元素.本文的证明使用了有穷损害优先方法.§1.定义1.任给A、B,若P~A (?)P~B(即A(?)_t~p B),则记为A(?)B;若A(?)B 或B(?)A,则称A、B可比较,否则称为不可比较,并记为A|B.2.称A 为密度可测,如果存在一个可计算函数d,使得(1)对任意多项式p,都可能行地找到无穷个n 使p(n)