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)
“No testing has overtaken you that is not common to everyone. God is faithful, and he will not let you be tested beyond your strength, but with the testing he will also provide the way out so that you may be able to endure it.”
—Bible: New Testament, 1 Corinthians 10:13.