Characterization of problems for which sublinear time algorithms exist
For the constant-time task of testing graph properties, an interesting characterization is known. A graph property is a function from all graphs to $\{0,1\}$, and a graph property $P$ is testable if there is a randomized algorithm $A$ such that for all $\varepsilon &gt; 0$ and all graphs $G$:


$A(G)$ reads only $g(\varepsilon)$ edges of $G$ for some function $g$
If $P(G)=1$ then $A(G)$ outputs ``yes'' with high probability (say, at least $2/3$)
If at least $\varepsilon n^2$ edges of $G$ have to be added or removed in order to get a $G&#39;$ such that $P(G&#39;)=1$ (that is, $G$ is $\varepsilon$-far from the property) then $A(G)$ outputs ``no'' with probability at least $2/3$


That is, $A$ can distinguish between graphs which have $P$ and graphs which have high edit distance from graphs having $P$. Alon, Fischer, Newman, and Shapira proved that a property $P$ is testable in this way if and only if the property can be "reduced" to the property of checking whether a graph has an $\varepsilon$-regular partition (in the sense of Szemeredi). This shows that testing regularity is "complete" for testing, in some sense. (There is also a one-sided error version of testability, see the reference.)