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)\geq q(n)$, we construct properties with query complexity $\widetilde{\Theta}(q(n))$ and time complexity $\widetilde\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.

We then turn to halfspaces in $\mathbb{R}^d$, a fundamental class in property testing and learning theory. We study the problem of approximating the distance from the input function to the nearest halfspace within additive error $\epsilon$. (The distance approximation problem is known to have roughly the same complexity as tolerant property testing for appropriate setting of parameters.) For the distribution-free distance approximation problem, known algorithms achieve query complexity $O(d/\epsilon^2)$, but run in time $\widetilde{\Theta}(1/\epsilon^d)$. We provide a fine-grained justification for this gap: assuming the (integer) $k$-SUM conjecture, any algorithm must have running time $(1/\epsilon)^{\lceil (d+1)/2 \rceil -o(1)}$. This fine-grained lower bound yields a provable (under a well-established assumption) separation between query and time complexity for a natural and well-studied (tolerant) testing problem. We also prove that any randomized Statistical Query (SQ) algorithm under the standard Gaussian distribution requires $(1/\epsilon)^{\Omega(d)}$ queries if the queries are answered with additive error up to $\epsilon^{\Omega(d)}$, revealing a fundamental barrier even in the distribution-specific setting.