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 distinguish if some combinatorial structure S (such as a graph or a boolean function) satisfies some property P, or is "far" from having this property (meaning an ε-fraction of the representation of S need be modified in order 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 G on n vertices, decide if G is bipartite, or G cannot be made bipartite even after removing an arbitrary subset of at most edges of G."
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.