The bounded-degree query model, introduced by Goldreich and Ron (\textit{Algorithmica, 2002}), is a standard framework in graph property testing and sublinear-time algorithms. Many properties studied in this model, such as bipartiteness and 3-colorability of graphs, can be expressed as satisfiability of constraint satisfaction problems (CSPs). We prove that for the entire class of \emph{unbounded-width} CSPs, testing satisfiability requires $\Omega(n)$ queries in the bounded-degree model. This result unifies and generalizes several previous lower bounds. In particular, it applies to all CSPs that are known to be $\mathbf{NP}$-hard to solve, including $k$-colorability of $\ell$-uniform hypergraphs for any $k,\ell \ge 2$ with $(k,\ell) \neq (2,2)$. Our proof combines the techniques from Bogdanov, Obata, and Trevisan (\textit{FOCS, 2002}), who established the first $\Omega(n)$ query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra.

翻译：由Goldreich和Ron（《算法学，2002年》）提出的有界度查询模型是图性质测试和亚线性时间算法领域的标准框架。该模型中研究的许多性质，如图的二部性和3-可着色性，均可表达为约束满足问题（CSP）的可满足性。我们证明，对于整个无界宽度CSP类，在有界度模型中测试可满足性需要Ω(n)次查询。该结果统一并推广了多个先前的下界结论。特别地，它适用于所有已知为NP难解的CSP，包括任意k,ℓ ≥ 2且(k,ℓ) ≠ (2,2)时ℓ-均匀超图的k-可着色性问题。我们的证明结合了Bogdanov、Obata和Trevisan（《FOCS，2002年》）在有界度模型中建立首个CSP测试Ω(n)查询下界的技术，以及通用代数中的已知结果。