Эффективная сертификация

Как же формализовать идею о том, что решение задачи может быть проверено эф- фективно независимо от того, насколько эффективно может решаться сама задача? Структура «алгоритма проверки» для задачи X отличается от структуры алгоритма, ищущего решение; для «проверки» решения необходима входная строка 5 и от- дельная строка t («сертификат»), доказывающая, что 5 является «положительным» экземпляром X.

Итак, алгоритм B называется эффективным сертифицирующим алгоритмом для задачи X, если он обладает следующими свойствами:

♦ B — алгоритм с полиномиальным временем, получающий два входных аргу- мента 5 и t;

♦ существует такая полиномиальная функция р, что для каждой строки 5 усло- вие 5 X выполняется в том, и только в том случае, если существует строка t, для которой |t < P (5|) и B(5, t) = да.

Чтобы понять, о чем в действительности говорит это определение, потребуется некоторое время. Эффективный сертифицирующий алгоритм следует рассма- тривать как подход к задаче X с «управленческой» точки зрения. Он не пытается самостоятельно решить, принадлежит ли входная строка 5 множеству X. Вместо этого он эффективно оценивает предлагаемые «доказательства» t, что 5 принад- лежит X (при условии, что они не слишком длинные), и он является правильным алгоритмом в том слабом смысле, что 5 принадлежит X тогда, и только тогда, когда существует доказательство, которое его в этом убедит.

Эффективный сертифицирующий алгоритм B может использоваться как цен- тральный компонент алгоритма «грубой силы» для задачи X: для входной стро- ки 5 проверить все строки t длины < P (| 5 |) и проверить, выполняется ли условие B(5, t) = да для каких-либо из этих строк. Однако существование B не дает никакого очевидного способа построения эффективного алгоритма, который решает X; в кон- це концов, мы еще должны найти строку t, для которой B(5, t) вернет ответ «да», а количество возможностей для t экспоненциально велико.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Эффективная сертификация:

  1. 1.4. Лицензирование, стандартизация и сертификация
  2. 1.4.3. Сертификация
  3. Эффективность социальной работы
  4. Эффективность
  5. ЭФФЕКТИВНОСТЬ
  6. Оценка эффективности нововведения.
  7. Эффективность допроса
  8. 1.3. Критерии эффективности фокусированного интервью
  9. Психологические условия эффективной требовательности.
  10. ЭФФЕКТИВНЫЕ ПРИЕМЫ ПРОДАЖИ ТОВАРОВ
  11. Критерии оценки эффективности деятельности социального работника
  12. Глава 1 Духовно-правовая идеология – основа эффективного воспитания
  13. КАК ПОВЫСИТЬ ЭФФЕКТИВНОСТЬ СВОИХ ДЕЙСТВИЙ