Вспомните, что доказательство можно рассматривать как своего рода расчет — чисто механический процесс, выплевывающий готовые теоремы. Но что вы скажете о расчете, который ошибается с вероятностью 2–1000, — это доказательство или нет? То есть можно ли считать расчеты в классе BPP законными доказательствами? Ну, если мы сумеем сделать вероятность ошибки такой маленькой, что скорее комета попадет в наш компьютер и разобьет его вдребезги, чем он ошибется в доказательстве, то такой вариант, безусловно, кажется допустимым!
А помните NP — класс задач с полиномиального размера сертификатами (для ответа «да»), которые можно проверить за полиномиальное время? А раз мы думаем о рандомизированных алгоритмах, сама собой возникает идея «совместить» NP и BPP и создать таким образом новый класс сложности, где вы получаете полиномиального размера сертификат на ответ «да» и можете использовать для проверки этого сертификата рандомизированный алгоритм полиномиального времени. Так вот, такой гибридный класс действительно был предложен Ласло Бабаи в 1980-е гг. Но вы, вероятно, ни за что не догадаетесь, как Бабаи назвал свой класс, если не знаете этого заранее. Сдаетесь? Он называется MA — «Мерлин — Артур». Бабаи видел это как игру, где «Мерлин» — всемогущий, но ненадежный доказывающий маг, — снабжает нас сертификатом полиномиального размера, а затем «Артур» — скептически настроенный король полиномиального времени — запускает рандомизированный алгоритм для проверки мерлинова сертификата. Более формально MA можно определить как класс языков L, для которых существует рандомизированный алгоритм полиномиального времени V для Мерлина, такой, что для любого x:
1. Если x ∈ L, то существует по крайней мере один сертификат w, такой, что V(x, w) принимает наверняка.
2. Если x ∉ L, то, вне зависимости от w, V(x, w) отвергает с вероятностью по крайней мере 1/2.
Оказывается, если заменить в пункте 1 «наверняка» на «с вероятностью не менее 2/3», то получится в точности тот же класс MA. (Доказательство этого занимает страницу-другую, поэтому мы не будем здесь его приводить.) Можно показать также, что NP и BPP содержатся в MA и что MA содержится в PP и Σ2P ∩ П2P.
Теперь, когда у нас появились персонажи Мерлин и Артур, мы можем определить также и более интересные игры. В частности, предположим, что Артур должен послать Мерлину случайный вызов, на который тот должен ответить. Тогда вы получаете новый класс под названием AM («Артур — Мерлин»), который содержит в себе MA, но не факт, что совпадает с ним и, в свою очередь, содержится в П2P. На самом деле должен сказать, что большинство из нас сегодня предполагают, что NP = MA = AM; в самом деле, известно, что это следует из гипотезы о нижней оценке сложности схемы — аналогично тому, как утверждается равенство P = BPP (см. главу 7). Но пока мы очень далеки от возможности доказать это.
Вы можете задаться вопросом: что происходит, если после получения ответа от Мерлина Артур задает Мерлину следующий вопрос или три-четыре следующих вопроса? Можно подумать, что в этом случае Мерлин смог бы доказать Артуру даже больше, верно? Неверно! Еще одна удивительная теорема гласит, что AM = AMAM = AMAMAM…, то есть любое фиксированное число вопросов Мерлину имеет ровно ту же силу, что и один вопрос.