Certifying algorithm

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, 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 <a href="/facts/Proof_checker/hjFGxLPn">proof checker</a> 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 <a href="/facts/Linear_time/77T62gmf">linear time</a>) 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 <a href="/facts/Formal_verification/BYD4GnJR">formal verification</a>.
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).

Certifying algorithm open-in-new

Certifying algorithm