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:
“Oh, had I received the education I desired, had I been bred to the profession of the law, I might have been a useful member of society, and instead of myself and my property being taken care of, I might have been a protector of the helpless, a pleader for the poor and unfortunate.”
—Sarah M. Grimke (1792–1873)
“Is this testing whether I’m a replicant or a lesbian, Mr. Deckard?”
—David Webb Peoples, U.S. screenwriter, and Ridley Scott. Rachel, Blade Runner, being tested to determine if she is human or machine (1982)