2010 | OriginalPaper | Chapter
Progress on Certifying Algorithms
Authors : Kurt Mehlhorn, Pascal Schweitzer
Published in: Frontiers in Algorithmics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A
certifying algorithm
is an algorithm that produces with each output, a
certificate
or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying program
P
(= the implementation of a certifying algorithm) inputs
x
, receives an output
y
and a certificate
w
, and then checks, either manually or by use of a checking program, that
w
proves that
y
is a correct output for input
x
. In this way, he/she can be sure of the correctness of the output without having to trust
P
. We refer the reader to the recent survey paper [9] for a detailed discussion of certifying algorithms.