怎样理解计算复杂性中的oracle?
所有的Oracle在本质上都是一样的，无论是量子算法、计算复杂性或者密码学。当我们考虑一种问题的难解性时，我们通常会问以下问题。给定一个需要求解的问题实例，也许我们没有容易的（多项式时间）解法。如果给一个Oracle（先知、神仙、预言机）来帮忙求解多项式个问题实例（这些问题可以具有相关性），那么，是否可以更容易地求解出所给定的难题。
例子：给你一个大整数N，要求把它分解成若干个小整数的乘积。同时，让你拥有Oracle，这个Oracle可以帮助你分解任何除N之外的大整数。请问，这个Oracle是否有帮助？
Oracle通常用于理论证明，实现的意义不大。鉴于直观上Oracle源自具体的问题，也可以在现实生活中找到Oracle的“实现”，比如，SSL协议的某些错误实现可认为是帮助攻击者解密的Oracle。
■网友
【怎样理解计算复杂性中的oracle?】 你应该已经知道怎么回事了，不过我还是想补充下前一个答案没提到的东西。
在量子算法里面，假设一个Oracle能实现，要么是有经典的知识证明这个东西在经典世界是可以有效实现的（进而对应到量子），要么很可能（公认或者符合直觉）在量子上可以有效实现。经典的计算复杂度我不大懂，不过在量子上用Oracle是把主要的精力放在算法的其他方面，毕竟一个量子算法的方方面面都考虑到的话会非常难设计。但Oracle的提出也是要“令人信服”的。
Grover算法的Oracle主要完成的是两步：1、按序号存储数据，对应于经典的存储；2、根据数据计算函数值，对应于经典上的一次查询。很多情况下这两步看成一步，直接按序号求函数值。
推荐阅读
![[科技小视线]天猫总裁蒋凡：新消费人口、消费供给是今年双11主要特征](https://imgcdn.toutiaoyule.com/20200406/20200406144244644102a_t.jpeg)
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 有啥方法，网站，项目可以自己练习计算广告学
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采