Property testing

Property testing is a field of theoretical computer science, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects.^[1]

A property testing algorithm for a decision problem is an algorithm whose query complexity (the number of queries made to its input) is much smaller than the instance size of the problem. Typically, property testing algorithms are used to determine whether some combinatorial structure $S$ (such as a graph or a boolean function) satisfies some property $P$ , or is "far" from having this property (meaning that an $ε$ -fraction of the representation of $S$ must be modified to make $S$ satisfy $P$ ), using only a small number of "local" queries to the object. ^[2]^[3]

For example, the following promise problem admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant $ε > 0$ ):

"Given a graph on

n

vertices, decide whether it is bipartite, or cannot be made bipartite even after removing an arbitrary subset of at most

εn 2

edges."

Property testing algorithms are central to the definition of probabilistically checkable proofs, as a probabilistically checkable proof is essentially a proof that can be verified by a property testing algorithm.

^ Cite error: The named reference g2017 was invoked but never defined (see the help page).
^ Cite error: The named reference as2008 was invoked but never defined (see the help page).
^ Cite error: The named reference g1999 was invoked but never defined (see the help page).

[g2017-1] Cite error: The named reference g2017 was invoked but never defined (see the help page).

[as2008-2] Cite error: The named reference as2008 was invoked but never defined (see the help page).

[g1999-3] Cite error: The named reference g1999 was invoked but never defined (see the help page).

[1]

[2]

[3]