认证算法

在理论计算机科学中，认证算法是一种算法，它与它所解决的问题的解决方案一起，输出一个证明该解决方案是正确的。如果一个认证算法和一个证明检查器的综合运行时间比同一问题的最佳非认证算法最多慢一个常数，那么这个认证算法就被认为是高效的。认证算法产生的证明在某种意义上应该比算法本身更简单，否则任何算法都可以被认为是认证的（其输出通过再次运行相同的算法进行验证）。有时，这被正式化为要求证明的验证比原始算法花费更少的时间，而对于其他问题（特别是那些可以在线性时间内找到解决方案的问题），输出证明的简单性在一个不太正式的意义上被考虑。例如，对于人类用户来说，输出证明的有效性可能比算法的正确性更明显，或者证明的检查器可能更适合于形式验证。认证算法的实现也包括算法产生的证明的检查器，这可能被认为比非认证算法更可靠。

可检查算法问题的许多例子都来自图论。例如，一个测试图是否为二元结构的经典算法将简单地输出一个布尔值：如果图是二元结构，则为真，否则为假。相比之下，一个认证算法可能会在图是两面体的情况下输出一个两面体的颜色，如果不是，则输出一个奇数长度的周期。任何图形都是二方的，当且仅当它可以被2-着色，而非二方的，当且仅当它包含一个奇数周期。检查一个2色是否有效和检查一个给定的奇长的顶点序列是否是一个周期，都可以比测试二元性更简单地进行。类似地，可以通过一个证明算法来测试一个给定的有向图是否是无周期的，该算法可以输出一个拓扑顺序或一个有向循环。

有可能通过一个认证算法来测试一个无向图是否是一个和弦图，该算法输出一个消除排序（一个所有顶点的排序，对于每个顶点来说，排序后面的邻居形成一个悬崖）或者一个无弦循环。而且可以通过一个证明算法来测试一个图是否是平面的，该算法可以输出一个平面嵌入或者一个Kuratowski子图。两个整数x和y的xxx公除数的扩展欧几里得算法是证明性的：它输出三个整数g（除数）、a和b，使ax+by=g。这个方程只能是xxx公除数的倍数，所以测试g是xxx公除数可以通过检查g是否同时除以x和y以及这个方程是否正确来进行。