3/3. Предыдущая часть 👆

Летописи свидетельствуют, что Мерлин недолго ждал следующего поручения.

Одним из нововведений Артура было внедрение вилок. Когда за Круглым Столом накрывали ужин, благородным рыцарям предлагалось оставить мечи и занять отведённые места. Некоторые с удовольствием поедали сочные бараньи ножки, легко доставаемые с помощью прочных вилок. Однако другие быстро нашли более «рыцарское» применение новым приборам и без промедления начали сводить счёты с соседями.

Артуру показалось, что манеры за столом можно было бы значительно улучшить с правильной рассадкой рыцарей. Как и прежде, он вызвал RSA (Royal Secret Agent), который составил граф, показывающий, кто с кем сможет сидеть мирно. Задача найти подходящую рассадку (то, что позже назовут гамильтоновым циклом в графе) снова была поручена Мерлину.

Когда Мерлин понял, что решения нет, он больше не стал прибегать к трюку с 150! диаграммами — он просто написал Кёнигу. Но либо почта шла слишком медленна, либо возникло другое препятствие — ответа Кёнига на это письмо так и не поступило. Не сумев представить решение в установленный срок, Мерлин был приговорён к виселице. Однако приговор был немедленно заменён на «вечность в темнице с возможностью условного освобождения после отбытия одной трети срока».

(c) László Babai
🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

Это была наша новая рубрика #ВГостяхУСказки, а так же подводка к следующему посту про класс сложности IP (интерактивные доказательства - маг Мерлин с безграничными интеллектуальными возможностями и полиномиальный король Артур), а так же про удивительное доказательство теоремы IP=PSPACE.

#Complexity #IP #PSPACE #IPvsPSPACE

2/2. Продолжение. Начало тут 👆

Почему это важно? Во-первых, этот реультат контр-интуитивный. Считалось, что класс IP это где-то между NP и PSPACE, чуть больше NP, но и близко не дотягивает до PSPACE.

IP - это проверяющий с ограниченным полиномиальным временем мышлением, как король Артур (полином от времени/числа шагов и немного рандома) и неограниченный в вычислительных возможностях доказывающий оракул с сверхспособностями, как Мерлин.

Артур может быть убеждён в любых вещах уровня PSPACE (а это мощный класс задач, например, шахматы), если общается с могучим доказывающим (Мерлин). Это радикально изменило понимание того, насколько мощными могут быть системы доказательств, даже с очень ограниченным проверяющим.

С опорой на классическую PSPACE-полноту задачи верификации кванторной булевой формулы (QBF), Шамир дал то, чего Мерлину так не хватало — мощный, вероятностный протокол убеждения. И у Мерлина появился шанс снова оказаться на свободе.

🖨️ Пока старенький принтер печатал короткий документ, Мерлин завершил вычисления и написал письмо Артуру:

Дата: 26 дек 89, 19:42:14 BST
От: merlin@cave
Кому: arthur

Сир,
в отдельном сообщении я отправляю вам
матрицу M порядка 103 680 300 с элементами
из множества {-1, 0, 1, 2, 3}. Со ссылкой на
L.G. Valiant, TCS 8 (1979), стр. 189–201,
вы без труда убедитесь, что перманент
матрицы M равен 2^{43 200 000}, умноженному
на количество гамильтоновых циклов в
«графе рассадки».

Дайте знать, когда у вас будет время
на полиномиальные вычисления.
С вероятностью 1 - 2^{-1000}
я уверю вас, что этот перманент равен нулю.

Освежите свои знания по линейной алгебре, правилу Горнера, и держите игральные кости наготове.

С уважением,
Мерлин

P.S. Спасибо за подключение к сети.
P.P.S. Что касается компенсации — мне хватит позиции в университете Чикаго.

📍Теперь Мерлин держит путь к Новому Свету. Сначала — Йель (он знал кого-то в тех краях), потом — Великие озёра (Great Lakes).

🍀 Пожелаем ему попутного ветра и продуктивных интеракций.

🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

@easy_about_complex

#ВГостяхУСказки #Complexity #IP #PSPACE #IPvsPSPACE