Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Property_testing> ?p ?o. }
Showing items 1 to 33 of
33
with 100 items per page.
- Property_testing abstract "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.".
- Property_testing wikiPageExternalLink ron00property.html.
- Property_testing wikiPageExternalLink download?doi=10.1.1.39.6933&rep=rep1&type=pdf.
- Property_testing wikiPageExternalLink paper-removal.pdf.
- Property_testing wikiPageExternalLink icm.ps.
- Property_testing wikiPageExternalLink testSU.ps.
- Property_testing wikiPageID "20506304".
- Property_testing wikiPageRevisionID "599177963".
- Property_testing hasPhotoCollection Property_testing.
- Property_testing subject Category:Approximation_algorithms.
- Property_testing subject Category:Randomized_algorithms.
- Property_testing subject Category:Theoretical_computer_science.
- Property_testing type Abstraction100002137.
- Property_testing type Act100030358.
- Property_testing type Activity100407535.
- Property_testing type Algorithm105847438.
- Property_testing type ApproximationAlgorithms.
- Property_testing type Event100029378.
- Property_testing type Procedure101023820.
- Property_testing type PsychologicalFeature100023100.
- Property_testing type Rule105846932.
- Property_testing type YagoPermanentlyLocatedEntity.
- Property_testing comment "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.".
- Property_testing label "Property testing".
- Property_testing label "Test de propriété".
- Property_testing label "اختبار الخاصية".
- Property_testing sameAs Test_de_propriété.
- Property_testing sameAs m.04z_7r6.
- Property_testing sameAs Q2918980.
- Property_testing sameAs Q2918980.
- Property_testing sameAs Property_testing.
- Property_testing wasDerivedFrom Property_testing?oldid=599177963.
- Property_testing isPrimaryTopicOf Property_testing.