Certifying algorithm とは

理論的なコンピュータ科学では、認証アルゴリズムは、それが解決する問題の解決策とともに、解決策が正しいという証拠を出力するアルゴリズムである。証明アルゴリズムは、アルゴリズムの証明されたランタイムとプルーフチェッカーの組み合わせランタイムが同じ問題の最もよく知られている非証明アルゴリズムよりも最大で一定の要素だけ遅い場合に効率的であると言われています。
証明アルゴリズムによって生成された証明は、ある意味ではアルゴリズム自体よりも簡単でなければなりません。そうでなければ、どのアルゴリズムも証明と見なすことができます(同じアルゴリズムを再度実行して出力を検証します)。時には、これは、証明の検証が元のアルゴリズムより短い時間で済むように要求することによって形式化されることがありますが、他の問題(特に解が線形時間で見つかるもの)では、出力証明の単純さは、センス。例えば、出力証明の妥当性は、アルゴリズムの正しさよりも人間のユーザにとってより明らかであり得るか、または証明に対するチェッカーは、正式な検証により適している可能性がある。
アルゴリズムによって生成された証明のチェッカーも含む証明アルゴリズムの実装は、非認証アルゴリズムよりも信頼性が高いと考えることができる。アルゴリズムが実行されるたびに、正しい出力(望ましい場合)を生成し、アルゴリズムまたはその含意(望ましくないが一般的にバグを検出することなく続行することが望ましい)のバグを検出するか、アルゴリズムとチェッカーの両方が欠陥を隠し、それが検出されないようにする(望ましくないが、2つの独立したバグの存在に依存するとは考えにくい)。