Computational Complexity in Property Testing

We initiate a systematic study of the computational complexity of property testing, focusing on the relationship between query and time complexity. While traditional work in property testing has emphasized query complexity—often via information-theoretic techniques—relatively little is known about the computational hardness of property testers. Our goal is to chart the landscape of time-query interplay and develop tools for proving time complexity lower bounds. Our first contribution is a pair of time-query hierarchy theorems for property testing. For all suitable nondecreasing functions \(q(n)\) and \(t(n)\) with \(t(n) \ge q(n)\), we construct properties with query complexity \(\tilde \Theta(q(n))\) and time complexity \(\tilde \Omega(t(n))\). Our weak hierarchy holds unconditionally, whereas the strong version—assuming the Strong Exponential Time Hypothesis— provides better control over the time complexity of the constructed properties.