We prove two sets of results concerning computational complexity classes. The first concerns a variation of the random oracle hypothesis posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, P not equal NP with probability 1. This hypothesis was quickly disproven in several ways, most famously in 1992 with the result that IP equals PSPACE, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be ``large'' using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating NP and co-NP is not small, and obtain similar results for the separation of PSPACE from PH along with the separation of NP from BQP. We demonstrate that this version of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here. Second, we example the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy.
翻译:在计算复杂等级方面,我们证明有两套结果。第一套是Bennett和Gill提出的随机神器假设的变异。第一套是Bennett和Gill提出的随机神器假设,它们表明,相对于随机选择的神器,P并不等于NP和概率1。这一假设以几种方式迅速得到否认,最著名的是1992年,其结果是IP等同于PSPACE,尽管分类与概率不相等。第一,我们在这里建议用Ellentuck的地形学来变换“大”的含义。在这一新的背景下,我们证明将NP和共同NP(PNP)分离的神器组并不小,并获得类似的结果,将PSPACE与PH分离,同时将PPPPP与BQP分离。我们证明,这一假设的版本将它变成一个足够的条件,至少在这里审议的三个案例中,它变成了一个充分的条件。第二,我们举例说明提供这些不同等级分类分类的描述的复杂性,并确定它们在Borel等级中的确切位置。