随机化归约

随机化归约（randomized reduction），计算机科学技术名词，给定语言 A，B ，如果存在一个概率图灵机 M ，使对一切 x ，， M(x) 的时间期望是，那么称 A 随机化多项式时间归约于 B ，记为 ，这里 和分别是 B 和 A 的特征函数。