# Hardness vs testability ?

How does hardness plays role in testability?

Intuitively, it seems that for the problems which have exact efficient algorithm, there is more hope to get constant query (or, relatively a small number of queries) testing algorithm (in property testing framework).

But here is the counterexample, testing if a graph is $k$-colorable (which is a hard problem) there is a constant query testing algorithm (see paper), while for testing if given numbers are sorted $O(\frac{1}{\epsilon}\lg n)$ queries are required (see paper) .

So, does hardness plays any role in testability, or is completely orthogonal to it?