In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to decide if some mathematical object (such as a graph or a boolean function) has a "global" property, or is "far" from having this property, using only a small number of "local" queries to the object.
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 important in the theory of probabilistically checkable proofs.
Read more about Property Testing: Definition and Variants, Features and Limitations
Famous quotes containing the words property and/or testing:
“It is a well-settled principle of the international code that where one nation owes another a liquidated debt which it refuses or neglects to pay the aggrieved party may seize on the property belonging to the other, its citizens or subjects, sufficient to pay the debt without giving just cause of war.”
—Andrew Jackson (1767–1845)
“Traditional scientific method has always been at the very best 20-20 hindsight. It’s good for seeing where you’ve been. It’s good for testing the truth of what you think you know, but it can’t tell you where you ought to go.”
—Robert M. Pirsig (b. 1928)