Randomness, Relativizations, and Polynomial Reducibilities
Randomness, Relativizations, and Polynomial Reducibilities
复制标题
随机性、相对化和多项式约简
DOI：
10.1007/3-540-16486-3_87
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
K. Ambos
中科院分区：
文献类型：
--
作者：
K. Ambos
我们证明了，对于任何不能在多项式时间内计算的集合A，与A不可比的集合类p-多-一具有测度1，而在p-图灵约简的情况下，与A不可比的集合类具有测度1当且仅当A不在BPP类中，BPP类是一类可以在多项式时间内以一致有界错误概率求解的问题.一个随机选择的一对问题之间的reducibility关系的后果进行了讨论。此外，它表明，任何类，这在相对化的情况下崩溃的概率为P，实际上是包含在BPP。
We show that, for any set A which cannot be computed in polynomial time, the class of sets p-many-one incomparable with A has measure 1, whereas in case of p-Turing reducibility the class of sets incomparable with A has measure 1 if and only if A is not in the class BPP, the class of problems which can be probabilisticly solved with uniformly bounded error probability in polynomial time. Consequences for the reducibility relation between a randomly chosen pair of problems are discussed. Moreover, it is shown that any class, which in the relativized case collapses to P with probability one, is actually contained in BPP.