This HTML5 document contains 40 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n11https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Sanity_check
dbo:wikiPageWikiLink
dbr:Certifying_algorithm
Subject Item
dbr:Library_of_Efficient_Data_types_and_Algorithms
dbo:wikiPageWikiLink
dbr:Certifying_algorithm
Subject Item
dbr:Certifying_algorithm
rdfs:label
Certifying algorithm
rdfs:comment
In theoretical computer science, a certifying algorithm is an algorithm that outputs, together with a solution to the problem it solves, a proof that the solution is correct. A certifying algorithm is said to be efficient if the combined runtime of the algorithm and a proof checker is slower by at most a constant factor than the best known non-certifying algorithm for the same problem.
dcterms:subject
dbc:Error_detection_and_correction dbc:Algorithms dbc:Software_testing
dbo:wikiPageID
51386092
dbo:wikiPageRevisionID
916259824
dbo:wikiPageWikiLink
dbc:Error_detection_and_correction dbr:Bipartite_graph dbr:Greatest_common_divisor dbr:Formal_verification dbr:Clique_(graph_theory) dbr:Graph_theory dbr:Topological_sorting dbr:Planar_graph dbc:Software_testing dbr:Kuratowski's_theorem dbr:Chordal_graph dbr:Linear_time dbr:Directed_acyclic_graph dbr:Proof_checker dbr:Sanity_check dbr:Theoretical_computer_science dbr:Extended_Euclidean_algorithm dbc:Algorithms
owl:sameAs
n11:2e733 yago-res:Certifying_algorithm wikidata:Q28455530
dbp:wikiPageUsesTemplate
dbt:Math dbt:Mvar dbt:Reflist dbt:=
dbo:abstract
In theoretical computer science, a certifying algorithm is an algorithm that outputs, together with a solution to the problem it solves, a proof that the solution is correct. A certifying algorithm is said to be efficient if the combined runtime of the algorithm and a proof checker is slower by at most a constant factor than the best known non-certifying algorithm for the same problem. The proof produced by a certifying algorithm should be in some sense simpler than the algorithm itself, for otherwise any algorithm could be considered certifying (with its output verified by running the same algorithm again). Sometimes this is formalized by requiring that a verification of the proof take less time than the original algorithm, while for other problems (in particular those for which the solution can be found in linear time) simplicity of the output proof is considered in a less formal sense. For instance, the validity of the output proof may be more apparent to human users than the correctness of the algorithm, or a checker for the proof may be more amenable to formal verification. Implementations of certifying algorithms that also include a checker for the proof generated by the algorithm may be considered to be more reliable than non-certifying algorithms. For, whenever the algorithm is run, one of three things happens: it produces a correct output (the desired case), it detects a bug in the algorithm or its implication (undesired, but generally preferable to continuing without detecting the bug), or both the algorithm and the checker are faulty in a way that masks the bug and prevents it from being detected (undesired, but unlikely as it depends on the existence of two independent bugs).
prov:wasDerivedFrom
wikipedia-en:Certifying_algorithm?oldid=916259824&ns=0
dbo:wikiPageLength
4899
foaf:isPrimaryTopicOf
wikipedia-en:Certifying_algorithm
Subject Item
dbr:Extended_Euclidean_algorithm
dbo:wikiPageWikiLink
dbr:Certifying_algorithm
Subject Item
wikipedia-en:Certifying_algorithm
foaf:primaryTopic
dbr:Certifying_algorithm