论文标题
置换之间关系的可检验性
Testability of relations between permutations
论文作者
论文摘要
我们启动有关置换之间关系的财产测试问题的研究。在此类问题中，输入是元组$（σ_1，\ dotsc，σ_d）$ $ \ {1，\ dotsc，n \} $，并且希望确定此元组是否满足某种关系$ e $，还是远离满足$ e $ e $ $ e $ $ e $的每个元素。如果仅通过查询给定排列的少量条目来解决此计算问题，我们说$ e $是可测试的。例如，当$ d = 2 $和$ e $由单个关系$ \ mathsf {xy = yx} $组成时，这对应于测试$σ_1σ_2=σ_2σ_1$，其中$σ_1σ_2$和$σ_2σ_1$表示排入的构图。 我们定义了与系统$ e $自然关联的图表集合，该图表编码与$ e $的可测试性相关的所有信息。然后，我们证明了两个定理，这些定理在这些图的膨胀属性方面提供了可检验性和非检测性的标准。由于与群体理论有着深厚的联系，这两个定理都适用于广泛的关系系统。 此外，我们将置换量的稳定性的稳定性理论概念提出为上述可检验性概念的特殊情况，将所有先前关于稳定性的作品解释为可检验性结果，从计算角度来调查先前关于稳定性的结果，并描述了许多关于稳定性和可检验性研究的方向。
We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple $(σ_1,\dotsc,σ_d)$ of permutations on $\{1,\dotsc,n\}$, and one wishes to determine whether this tuple satisfies a certain system of relations $E$, or is far from every tuple that satisfies $E$. If this computational problem can be solved by querying only a small number of entries of the given permutations, we say that $E$ is testable. For example, when $d=2$ and $E$ consists of the single relation $\mathsf{XY=YX}$, this corresponds to testing whether $σ_1σ_2=σ_2σ_1$, where $σ_1σ_2$ and $σ_2σ_1$ denote composition of permutations. We define a collection of graphs, naturally associated with the system $E$, that encodes all the information relevant to the testability of $E$. We then prove two theorems that provide criteria for testability and non-testability in terms of expansion properties of these graphs. By virtue of a deep connection with group theory, both theorems are applicable to wide classes of systems of relations. In addition, we formulate the well-studied group-theoretic notion of stability in permutations as a special case of the testability notion above, interpret all previous works on stability as testability results, survey previous results on stability from a computational perspective, and describe many directions for future research on stability and testability.
