相對化複雜性類

相對化複雜性類(relativized complexity class一種複雜性類.指由帶外部信息源的圖靈機所接受(計算)的複雜性類.設MA為帶外部信息源A的圖靈機.}M為其複雜性測度，f為遞歸函式，則複雜性類}`'(f>-}L}若存在帶A為外部信息源的圖靈機M"接受L，並且f為M"的(關於}M的)界函式}便是一個相對化(於A)的複雜性類，記為CA.特別地，
P" =DTIMEA (pol，NPA=NTIMEA(pol).其中pol表示多項式函式類.