Эффективная сертификация
Как же формализовать идею о том, что решение задачи может быть проверено эффективно независимо от того, насколько эффективно может решаться сама задача?
Структура «алгоритма проверки» для задачи X отличается от структуры алгоритма, ищущего решение; для «проверки» решения необходима входная строка s и отдельная строка t («сертификат»), доказывающая, что s является «положительным» экземпляром X.
Итак, алгоритм B называется эффективным сертифицирующим алгоритмом для задачи X, если он обладает следующими свойствами:
- B — алгоритм с полиномиальным временем, получающий два входных аргумента s и t;
- существует такая полиномиальная функция p, что для каждой строки s условие s Ѯ X выполняется в том, и только в том случае, если существует строка t, для которой |t| ≤ P (|s|) и B(s, t) = да.
Чтобы понять, о чем в действительности говорит это определение, потребуется некоторое время. Эффективный сертифицирующий алгоритм следует рассматривать как подход к задаче X с «управленческой» точки зрения. Он не пытается самостоятельно решить, принадлежит ли входная строка s множеству X.
Вместо этого он эффективно оценивает предлагаемые «доказательства» t, что s принадлежит X (при условии, что они не слишком длинные), и он является правильным алгоритмом в том слабом смысле, что s принадлежит X тогда, и только тогда, когда существует доказательство, которое его в этом убедит.
Однако существование B не дает никакого очевидного способа построения эффективного алгоритма, который решает X; в конце концов, мы еще должны найти строку t, для которой B(s, t) вернет ответ «да», а количество возможностей для t экспоненциально велико.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу