在图属性测试和亚线性时间算法的标准框架中，Goldreich和Ron在2002年提出的有界度查询模型是一个重要的研究方向。许多在该模型中研究的属性，例如图的二分性和3-着色性，可以表达为约束满足问题（CSPs）的可满足性。
我们证明，对于整个$\textbf{无界宽度}$的CSP类，测试可满足性在有界度模型中需要$\Omega(n)$次查询。这一结果统一并推广了之前的多个下界，特别适用于所有已知是$\text{NP}$-困难的CSP，包括任何$k,l \geq 2$且$(k,l) \neq (2,2)$的$l$-均匀超图的$k$-着色性。
我们的证明结合了Bogdanov、Obata和Trevisan在2002年建立的第一个$\Omega(n)$查询下界的技术，以及来自通用代数的已知结果。
博主点评： 该研究为理解无界宽度CSP的复杂性提供了重要的理论基础，强调了在亚线性查询中测试可满足性的困难性，这对于图论和计算复杂性领域的研究者具有重要意义。通过结合已有的下界结果，该论文为未来的研究指明了方向。