摘 要: | 研究概率多项式时间谱系的结构性质,证明了:(1)如果BP∑_(k+1)~pBP∑_k~P,则PH=BP∑∏_K~P;(2)如果BP∑_k~PBP∏_k~P,则;PH=BP∑_K~PP;(3)对任意n,k≥0,BP∑_K~P(BP∑_n~P)=BP∑_(n+k)~p,BP∑_n~P(BP△_(k+1)~P)=BP∑_(n+k)~n;(4)对任意n,k≥1,BP∑_n~P(BP∑_k~p∩BP∏_k~P)=BP∑_(n+k-1)~P这些结果说明概率多项式时间谱系与多项式时间谱系有相同的结构性盾,但也有差别.
|