预言机

阐述

给定语言 $A$，预言机 $M^A$ 是一个修改的 Turing 机，当它将一个输入写到特制的黑箱纸带时，有一个黑箱能在一步内给出该输入是否属于语言 $A$ 的答案。

实例

• $P^A$ 是可以在多项式时间内由 A-预言机判定的语言集合
• $NP^A$ 类似

性质

相关内容

• $\mathrm{NP} \subseteq \mathrm{P}^{S A T}$
• $\operatorname{coNP} \subseteq \mathrm{P}^{S A T}$
• 存在一个黑盒 A 使得 $\mathrm{P}^{A} \neq \mathrm{NP}^{A}$
• 存在一个黑盒 B 使得 $\mathrm{P}^{B}=\mathrm{NP}^{B}$

由于这两条性质的存在，我们难以用对角化方法来证明 P = NP 或者 P ≠ NP。

参考文献