口试理论Info，一个3-SAT的问题。
本帖最后由 blurryblue 于 2010-5-14 15:07 编辑遇到对于3-SAT的问题，
目前已知最好的worst-case随机算法计算时间是O(1.333^n) ，还有些较复杂的算法优化到（1.322^n）
而deterministisch算法的时间是1.481^n（具体数值记不清，但肯定比1.333大）。
有没有人知道，为什么这里随机算法要比确定性算法更有效率？有没有相关的文章介绍？
回答简单的几句就行，用于口试。 {:4_276:}
页:
[1]