本文首先讨论“随机性”与“高效计算”之间的关系,并强调引入“随机性”于问题求解的意义与重要性。随后给出产生“随机性”的现实途径及为计算引入“随机性”的两种不同方式,即“在线”方式与“离线”方式;通过对概率图灵机求解判定问题的讨论,来说明两种引入“随机性”方式之间的等价关系。最后,本文指出现实的随机算法设计与实现并没有为计算引入真正的“随机性”。
科研之友
微信
新浪微博
Facebook
分享链接
