Сложность вычислений: дополнительные главы 2. Игры Артура-Мерлина. Теорема Голдвассер-Сипсера

00:00:00 - Игры Артура-Мерлина 00:05:10 - MA и AM 00:10:30 - Теорема об ускорении 00:16:17 - Теорема об идеальной полноте 00:17:55 - Теорема о MA и АМ в полиномиальной иерархии 00:18:55 - Теорема Голдвассер-Сипсера 00:21:25 - Следствия из пред. теорем 00:24:50 - Д-во т. о коллапсе AM-иерархии (об ускорении) 00:42:25 - Д-во теоремы об идеальной полноте Дата лекции: 12.02.26 Лектор: Мусатов Даниил Владимирович Оператор: Хаматов Платон Монтажер: Крещик Владимир Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvbvYD7vGggKC956fViF8b7v Плейлист