Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1
Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1
复制标题
相对于随机预言 A，PA != NPA != co-NPA，概率为 1
DOI：
--
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
John Gill
中科院分区：
文献类型：
--
作者：
Charles H. Bennett;John Gill
让A是通过为每个字符串x扔一个公平的硬币来随机选择的语言，以确定x是否属于A。 }^a $，$ {\ bf np}^a $，$ {\ bf pp}^a $，$ {\ textbf {pspace}}^a $在下一个中正确包含。另外，$ {\ bf np}^a \ ne {\ text {co-}} {\ bf np}^a $具有概率1。使用类$ {\ bf bpp}^a $ a $的概率甲骨文机器识别的语言，错误概率均匀地限制在$ \ tfrac {1} {2} $下方。 $ {\ bf np}^a $显示为1，概率1，包含$ {\ bf p}^a $ -immune Set，即，在$ {\ bf p}^a $中没有无限子集的集合。简要讨论了$ {\ bf p}^a $ - immunity与p-sparseness和$ {\ bf np}^a $ completeness：$ {\ bf p}^a $ -immune sets in $ {\ {\ bf np}^a $可能是稀疏或中等密度的，但不能是共同的。相对于随机长度放置置换$ \ pi $，而不是rand ...
Let A be a language chosen randomly by tossing a fair coin for each string x to determine whether x belongs to A. With probability 1, each of the relativized classes ${\textbf{LOGSPACE}}^A $, ${\bf P}^A $, ${\bf NP}^A $, ${\bf PP}^A $, and ${\textbf{PSPACE}}^A $ is properly contained in the next. Also, ${\bf NP}^A \ne {\text{co-}} {\bf NP}^A $ with probability 1. By contrast, with probability 1 the class ${\bf P}^A $ coincides with the class ${\bf BPP}^A $ of languages recognized by probabilistic oracle machines with error probability uniformly bounded below $\tfrac{1}{2}$. ${\bf NP}^A $ is shown, with probability 1, to contain a ${\bf P}^A $-immune set, i.e., a set having no infinite subset in ${\bf P}^A $. The relationship of ${\bf P}^A $-immunity to p-sparseness and ${\bf NP}^A $-completeness is briefly discussed: ${\bf P}^A $-immune sets in ${\bf NP}^A $ can be sparse or moderately dense, but not co-sparse. Relativization with respect to a random length-preserving permutation $\pi $, instead of a rand...