证书复杂性

（计算机科学技术）

证书复杂性（certificate complexity），计算机科学技术名词，给定，如果 f(x) =0，那么 x 的0-证书是 x 的位的一个系列，它证明 f(x) =0，如果 f(x) =1，那么 x 的1-证书是 x 的位的一个系列，它证明 f(x) =1， f 的证书复杂性定义为的最短0-或1-证书的长度｝。