Вероятностно проверяемое доказательство (PCP, Probabilistically checkable proof) — это еще одна невозможная на первый взгляд игра, в которую можно играть с концепцией «доказательства». Это доказательство, записанное таким способом, что вам, как ленивому проверяющему, достаточно вскрыть его в нескольких случайных местах, чтобы убедиться (в статистическом смысле) в его верности. Если вы хотите очень высокой уверенности в том, что это доказательство верно (скажем, с допустимой ошибкой в одну тысячную), вам никогда не придется проверять больше чем приблизительно тридцать битов. Разумеется, самое трудное здесь — закодировать доказательство так, чтобы это было возможно.

Вероятно, проще посмотреть это на примере. Помните задачу о неизоморфности графов? Мы покажем, что существует доказательство неизоморфности двух графов, такое, что любому проверяющему достаточно лишь взглянуть на постоянное число битов (хотя следует признать, что само доказательство при этом будет экспоненциально длинным).

Во-первых, если задана произвольная пара графов G₀ и G₁ с n узлами каждый, то доказывающий направляет проверяющему особым образом зашифрованную строку, доказывающую, что G₀ и G₁ неизоморфны. Что это за строка? Ну, мы можем выбрать некоторый вариант упорядочения всех возможных графов с n узлами, поэтому назовем i-й граф H_i. Затем доказывающий записывает в i-й бит строки нуль, если H_i изоморфен G₀, либо единицу, если H_i изоморфен G₁; в противном случае (если Hi неизоморфен ни одному, ни другому) он произвольно ставит на это место 0 или 1. Как эта строка доказывает проверяющему, что G₀ и G₁ неизоморфны? Просто: проверяющий бросает монетку, чтобы получить G₀ или G₁, и преобразует его случайным образом, чтобы получить новый граф H. Затем он запрашивает бит доказательства, соответствующий графу H, и принимает его в том и только том случае, если запрошенный бит соответствует первоначальному графу. Если G₀ и G₁ в самом деле неизоморфны, то проверяющий будет принимать всегда, а если нет, то вероятность принятия составит не более 1/2.

Надо отметить, что в этом примере доказательство получается экспоненциально длинным и работает только для неизоморфности графов. Какой же результат мы получаем в общем случае? Знаменитая теорема о вероятностно проверяемом доказательстве[101] гласит, что любая задача из NP принимает вероятностно проверяемые доказательства, более того, доказательства полиномиальной длины! Это означает, что всякое математическое доказательство может быть закодировано таком образом, чтобы любая ошибка в оригинальном доказательстве транслировалась в ошибки почти повсюду в новом доказательстве.

Понять это можно, например, через 3-SAT. Теорема о вероятностно проверяемом доказательстве эквивалентна NP-полноте задачи решения 3-SAT с априорной информацией о том, что либо формула удовлетворима, либо не существует набора входных переменных, который удовлетворял бы более чем (скажем) 90 % условий формулы. Почему? Потому что можно зашифровать вопрос о том, имеет ли некоторое математическое утверждение доказательство из не более чем n символов, в виде 3-SAT-реализации таким образом, что если существует валидное доказательство, то формула удовлетворима, а если нет, то никакое присваивание не удовлетворит более чем 90 % условий. Таким образом, для заданной входной строки нужно только отличить случай, при котором она удовлетворяет всем условиям, от случая, при котором она удовлетворяет не более чем 90 % из них, — а это можно сделать путем проверки нескольких десятков случайных условий, совершенно независимо от длины доказательства.