预言机 编辑
在计算复杂度理论与递归论中，预言机，又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为一个或多个黑盒子的图灵机，这个黑盒子的功能是可以在单一运算之内解答特定问题。预言者可以解答的问题，根据给定可以是任何复杂度类之内的问题。甚至可以使用不可判定问题，像是停机问题。
5
图片 0 图片
评论 0 评论
匿名用户 · [[ show_time(comment.timestamp) ]]
[[ nltobr(comment.content) ]]
相关
在密码学里面，随机预言机是一部预言机，对任何输入都回传一个真正均匀随机的输出，不过对相同的输入，该预言机每次都会用同一方法输出。换句话说，随机预言机是一个将所有可能输入与输出作随机映射的函数。
图灵归约是可计算性理论中的一种归约，若问题A可图灵归约成问题B，是指若问题B的解答已经知道，就可以解问题A，也可以解释为若一个算法可以用来处理问题B，就可以处理问题A。较正式的说法，可被图灵归约成问题B的问题是指若存在问题B的预言机，就可以求解的问题集合。图灵归约可以用在决定性问题及功能性问题。
在密码学里面，随机预言机是一部预言机，对任何输入都回传一个真正均匀随机的输出，不过对相同的输入，该预言机每次都会用同一方法输出。换句话说，随机预言机是一个将所有可能输入与输出作随机映射的函数。
计算复杂度理论中，多项式谱系是一个复杂度系列。它从P、NP和反NP复杂度类逐级产生至预言机。它类似于数理逻辑中算数阶层和分析阶层，只不过是由逐级放宽资源限制而产生的。