Certifying algorithm

A certifying algorithm is an algorithm that, in addition to producing a solution to the computational problem it solves, also outputs a proof or certificate that the solution is correct. In theoretical computer science, this certificate is meant to be checked by a separate, simpler proof-checking procedure whose own correctness is easy to establish, so that an incorrect answer from the main algorithm is caught rather than trusted. A certifying algorithm is considered efficient when the combined running time of the algorithm and its proof checker is no more than a constant factor slower than the best known algorithm for the same problem that does not produce a certificate, so correctness assurance is gained without a meaningful cost in performance.