Derandomization

释义 Definition

Derandomization（去随机化）：在算法或计算中，用确定性方法替代随机性，或在尽量保留效率的前提下，把原本依赖随机数的随机算法转化为确定性算法的过程与理论。常见于计算复杂性理论、伪随机性（pseudorandomness）、概率方法等领域。（在更宽泛语境中也可指“让过程不再随机”的做法，但学术语境最常用上述含义。）

发音 Pronunciation (IPA)

/diːˌrændəməˈzeɪʃən/

例句 Examples

Derandomization can turn a randomized algorithm into a deterministic one.
去随机化可以把随机算法转变为确定性算法。

Researchers study derandomization because it may reduce the gap between probabilistic and deterministic complexity classes.
研究人员研究去随机化，是因为它可能缩小概率型与确定性复杂度类之间的差距。

词源 Etymology

由前缀 **de-**（表示“去除、反向”）+ random（随机的）+ 名词后缀 -ization（……化、过程）构成，字面意思就是“把随机性去掉的过程”。该词在计算机科学中随“随机算法”与“伪随机生成器”等概念的发展而普及。

相关词 Related Words

• Deterministic
• Randomized
• Pseudorandom
• Pseudorandomness
• Randomness
• Monte Carlo
• Las Vegas
• Complexity
• Reduction
• Expander

文学与经典著作 Literary & Notable Works

• Nisan & Wigderson, Hardness vs. Randomness（关于“硬度与随机性”的经典论文，系统讨论去随机化思想与构造）
• Impagliazzo & Wigderson, P = BPP if E requires exponential circuits（去随机化与复杂度类关系的里程碑式结果之一）
• Motwani & Raghavan, Randomized Algorithms（随机算法经典教材，包含去随机化相关章节与方法）
• Arora & Barak, Computational Complexity: A Modern Approach（现代计算复杂性教材，专章讨论伪随机性与去随机化）
• Goldreich, Foundations of Cryptography（密码学基础著作中涉及伪随机性，与去随机化理论有紧密关联）