Formally, a property testing algorithm with query complexity q(n) and proximity parameter ε for a decision problem L is a randomized algorithm that, on input x (an instance of L) makes at most q(|x|) queries to x and behaves as follows: Here, "x is ε-far from L" means that the Hamming distance between x and any string in L is at least ε |x|.
A property testing algorithm is said to have one-sided error if it satisfies the stronger condition that the accepting probability for instances x ∈ L is 1 instead of 2/3.
Finally, without making any additional queries (but possibly using its randomness), the algorithm decides whether to accept or reject the input.
Typically, the goal is first to make the query complexity as small as possible as a function of the instance size n, and then study the dependency on the proximity parameter ε.
Unlike other complexity-theoretic settings, the asymptotic query complexity of property testing algorithms is affected dramatically by the representation of instances.
For example, when ε = 0.01, the problem of testing bipartiteness of dense graphs (which are represented by their adjacency matrix) admits an algorithm of constant query complexity.
In contrast, sparse graphs on n vertices (which are represented by their adjacency list) require property testing algorithms of query complexity Ω(n1/2).
Under a reasonable representation of graphs, this is equivalent to the earlier Hamming distance definition (up to possibly a change of constants).
To make precise the general notions of property testing in the context of graphs, we say a tester for graph property P should distinguish with at least ⅔ probability between the cases of G satisfying P and the cases where G is ε-far in edit distance from satisfying P. The tester can access some oracle to query whether a pair of vertices has an edge between them in G or not.
[4] In particular, the natural algorithms that sample a subgraph and check whether it satisfy the property are all correct, albeit with perhaps-suboptimal query complexities.
In the same paper, they showed that In this section, we will give some natural oblivious testing algorithms with one-sided error for triangle-freeness, bipartiteness, and k-colorability.
The latter is often exponential (as is the case of both) due to a lack of polynomial time decision algorithm to test the property on the induced subgraph.