多项式时间谱系和外部信息源A∈PH/Poly

可计算复杂性理论的一个中心问题是多项式时间谱系是否崩溃.Balc(?)zar、Book和Sch(?)ning在文献1]中利用稀疏集作为外部信息源研究了这个问题,他们证明了如下重要定