2
$\begingroup$

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?

$\endgroup$

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.