4.3.3 随机化与 P 类的关系：去随机化（Derandomization）猜想

文档摘要

4.3.3 随机化与 P 类的关系：去随机化（Derandomization）猜想 4.3.3 随机化与 P 类的关系：去随机化（Derandomization）猜想想象一下，你正站在计算理论的十字路口，一边是确定性算法的铁律，一边是随机化算法的灵光乍现。随机化算法如同一把双刃剑：它让原本NP-hard的问题在实践中飞速求解，却总让人质疑——这把剑的锋芒，真的离不开那份“随机”的不确定性吗？去随机化猜想，正是这个领域的核心谜题。它断言，如果我们能构造出足够强大的伪随机生成器（PRG），那些依赖随机性的P类扩展——如BPP（Bounded-error Probabilistic Polynomial time）——就能被“驯服”，纳入纯粹的确定性P类之内。