Bennett和Gill(1981)的古典结果表明,概率1,P^A≠ ≠ NP^A相对于随机神谕A,概率1,P^π≠ NP^π∩ coNP^π相对于随机排列π。 P^A = NP^A ∩ coNP^A 相对于随机神谕 A 是否保持开放。 虽然随机神谕分离已经扩展到特定的单个随机神谕 - 例如Martin-Löf随机或资源绑定的随机神谕 - 没有类似的结果以单独随机排列而闻名。 我们引入了一个新的资源边界度量框架,用于分析单个随机排列。 我们定义了排列马廷格尔和排列投注游戏,这些游戏表征了排列空间中的测量零集,从而实现了资源绑定随机排列的正式定义。 我们的主要结果表明,P^π≠ NP^π∩ coNP^π对于每个多项式时间投注游戏随机排列π。 这是相对于单个随机排列的第一个分离结果,而不是几乎无处不在的分离。 我们还通过显示每个多项式空间随机排列π的NP^π∩ coNP^π⊈BQP^π来加强Bennett,Bernstein,Brassard和Vazirani(1997)的量子分离。 我们研究随机排列和随机神谕之间的关系。 我们证明随机神谕是从随机排列中可还原的多项式时间。 相反,每个随机排列是否从随机神谕中还原,仍然打开。 我们表明,如果 NP ∩ coNP 不是 EXP 的可测量子集,那么 P^A ≠ NP^A ∩ coNP^A 相对于随机神谕 A 的概率为 1。 相反,用有时间限制的测量建立这种随机神谕分离意味着BPP是EXP的0子集。