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

Как же формализовать идею о том, что решение задачи может быть проверено эффективно независимо от того, насколько эффективно может решаться сама задача?

Структура «алгоритма проверки» для задачи 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: для входной строки s проверить все строки t длины ≤ P (| s |) и проверить, выполняется ли условие B(s, t) = да для каких-либо из этих строк.

Однако существование B не дает никакого очевидного способа построения эффективного алгоритма, который решает X; в конце концов, мы еще должны найти строку t, для которой B(s, t) вернет ответ «да», а количество возможностей для t экспоненциально велико.