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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.