Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Progress on Certifying Algorithms
verfasst von : Kurt Mehlhorn, Pascal Schweitzer
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.