Алгоритм сертификации - Certifying algorithm

В теоретическая информатика, а алгоритм сертификации - это алгоритм, который вместе с решением решаемой проблемы выводит доказательство того, что решение является правильным. Алгоритм сертификации называется эффективный если объединенное время выполнения алгоритма и корректор работает не более чем на постоянный коэффициент медленнее, чем самый известный алгоритм без сертификации для той же проблемы.^[1]

Доказательство, произведенное сертифицирующим алгоритмом, должно быть в некотором смысле проще, чем сам алгоритм, иначе любой алгоритм мог бы считаться сертифицирующим (с его выходными данными, проверенными повторным запуском того же алгоритма). Иногда это формализуется, требуя, чтобы проверка доказательства занимала меньше времени, чем исходный алгоритм, в то время как для других проблем (в частности, тех, решение которых можно найти в линейное время ) простота вывода доказательства рассматривается в менее формальном смысле.^[1] Например, достоверность выходного доказательства может быть более очевидной для пользователей-людей, чем правильность алгоритма, или средство проверки доказательства может быть более восприимчивым к формальная проверка.^[1][2]

Реализации алгоритмов сертификации, которые также включают средство проверки доказательств, сгенерированных алгоритмом, могут считаться более надежными, чем алгоритмы без сертификации. Ведь всякий раз, когда алгоритм запускается, происходит одно из трех: он производит правильный результат (желаемый случай), он обнаруживает ошибку в алгоритме или ее последствия (нежелательно, но обычно предпочтительнее, чем продолжать без обнаружения ошибки), или как алгоритм, так и средство проверки ошибочны таким образом, что ошибка маскируется и предотвращается ее обнаружение (нежелательно, но маловероятно, поскольку это зависит от наличия двух независимых ошибок).^[1]

Примеры

Многие примеры проблем с проверяемыми алгоритмами взяты из теория графов Например, классический алгоритм проверки правильности графа. двудольный просто выведет логическое значение: true, если граф двудольный, иначе false. Напротив, алгоритм сертификации может выдать двухкратную раскраску графа в случае, если он двудольный, или цикл нечетной длины, если это не так. Любой граф двудольный тогда и только тогда, когда он может быть двухцветным, и недвудольный тогда и только тогда, когда он содержит нечетный цикл. Как проверка допустимости 2-раскраски, так и проверка того, является ли данная последовательность вершин нечетной длины циклом, могут быть выполнены проще, чем проверка двудольности.^[1]

Аналогичным образом можно проверить, является ли данный ориентированный граф ациклический алгоритмом сертификации, который выводит либо топологический порядок или направленный цикл. Можно проверить, является ли неориентированный граф хордовый граф с помощью сертифицирующего алгоритма, который выводит либо порядок исключения (такой порядок всех вершин, что для каждой вершины соседи, находящиеся позже в порядке упорядочения, образуют клика ) или цикл без аккорда. И можно проверить, является ли график планарный с помощью сертификационного алгоритма, который выводит либо планарное вложение, либо Подграф Куратовского.^[1]

В расширенный алгоритм Евклида для наибольший общий делитель двух целых чисел Икс и у удостоверяет: выводит три целых числа грамм (делитель), а, и б, так что топор + к = грамм. Это уравнение может быть истинным только для кратных наибольшего общего делителя, поэтому проверка того, что грамм является наибольшим общим делителем, можно проверить, что грамм разделяет оба Икс и у и что это уравнение верно.^[1]

Смотрите также

• Санитарная проверка, простая проверка правильности выходного или промежуточного результата, которая не требуется для полного доказательства правильности

Рекомендации