属性测试

在计算机科学中，决策问题的属性测试算法是一种算法，其对其输入的查询复杂度远远小于问题的实例大小。典型的属性检验算法是用来区分某些组合结构S（如图或布尔函数）是否满足某种属性P，或者是否离这种属性很远（意味着需要修改S的表征的ε部分以使S满足P），只需使用对该对象的少量局部查询。例如，下面的承诺问题有一个算法，其查询复杂度与实例大小无关（对于一个任意的常数ε>0）。给定一个有n个顶点的图G，决定G是否是双联的，或者即使除去一个任意的子集，G也不能成为双联的，最多属性检验算法是概率可检验证明定义的核心，因为概率可检验证明本质上是一个可以被属性检验算法验证的证明。

形式上，对于一个决策问题L，具有查询复杂度q(n)和接近性参数ε的属性检验算法是一种随机算法，在输入x（L的一个实例）时，对x最多进行q(|x|)查询，其行为如下。如果x在L中，该算法以至少⅔的概率接受x；如果x离L有ε-far，该算法以至少⅔的概率拒绝x。这里，x离L有ε-far意味着x与L中任何字符串的汉明距离至少为ε|x|。如果一个属性检验算法满足更强的条件，即实例x∈L的接受概率是1而不是⅔，则称该算法具有单边错误。如果一个属性检验算法在观察到以前的查询的任何答案之前就执行了所有的查询，则被称为非自适应算法。这样的算法可以被看作是以下列方式运行的。首先，该算法接收其输入。在查看输入之前，利用其内部随机性，算法决定输入的哪些符号要被查询。接下来，该算法观察这些符号。最后，在不进行任何额外查询（但可能使用其随机性）的情况下，该算法决定是否接受或拒绝输入。

一个属性测试算法的主要效率参数是它的查询复杂度，它是在给定长度的所有输入（以及算法做出的所有随机选择）上检查的xxx输入符号数。人们对设计其查询复杂度尽可能小的算法感兴趣。在许多情况下，属性检测算法的运行时间是实例长度的亚线性。通常情况下，我们的目标是首先使查询复杂度作为实例大小n的函数尽可能小，然后研究对接近度参数ε的依赖性。与其他复杂度理论设置不同，属性测试算法的渐进查询复杂度受到实例表示法的极大影响。例如，当ε=0.01时，测试密集图（由其邻接矩阵表示）的二分性的问题就有一个恒定查询复杂度的算法。相反，n个顶点的稀疏图（由其邻接列表表示）需要查询复杂度的属性测试算法对于所有非琐碎的属性，属性测试算法的查询复杂度会随着接近度参数ε的变小而增长。

这种对ε的依赖是必要的，因为输入中少于ε的符号的变化不能用少于O(1/ε)的查询来以恒定的概率检测。密集图的许多有趣的属性可以用查询复杂度来测试，而查询复杂度只取决于ε，而不取决于图的大小n。例如，在很长一段时间内，测试图是否不包含任何三角形的最佳算法的查询复杂度是poly(1/ε)的塔函数，直到2010年才改进为log(1/ε)的塔函数。这种界限的巨大增长的原因之一是，许多关于图的属性检验的积极结果是利用Szemerédi正则性定理建立的，该定理的结论中也有塔式界限。