局部可检测编码

（计算机科学技术）

局部可检测编码（locally testable code），计算机科学技术名词，给定纠错码，称 E 是局部可检测的，如果存在常数 q ，多项式时间随机算法 C ，使得 C 查询一个字的最多 q 位，满足条件：①如果 y 是一个码字，则Pr［ C 接受 y ］=1；②否则， C 拒绝 y 的概率至少是 δ 的某个常数倍，这里 δ 是 y 离一切码字的最短距离。