И аккуратно разобрали более простые версии — сначала, как можно устроить справку, проверяемую с помощью факториала, а потом научились строить проверяющий для числа некоторую "справку о простоте" экспоненциально-полиномиальный многочлен.

Более того — решение десятой проблемы Гильберта как "любое перечислимое множество диофантово" устроено очень похоже на сведение к 3-SAT: чтобы нас убедить, что алгоритм -- машина Тьюринга, или, лучше, машина со счётчиками -- на данном входе хоть когда-нибудь останавливается, он приходит со справкой-сертификатом-протоколом своего выполнения, где (помимо всего прочего) записаны (в системе счисления с огромным основанием, "чтобы влезло") все состояния во все моменты времени. А многочлен проверяет, что все переходы действительно сделаны правильно (и для этого нужны ещё дополнительные переменные — они работают "справкой", удостоверяющей, что протокол-справка заполнен правильно).

===
Вернёмся теперь к тому, с чего мы начинали: к задаче о существовании у данного графа правильной трёхцветной раскраски — 3-COL. И поймём, что она тоже NP-полна.
Опять же, понятно, что это NP-задача — остаётся к ней любую из NP-полных задач свести. И конечно, сводить нужно 3-SAT — рисуя такой граф, чтобы его правильная раскраска соответствовала набору значений переменных, на котором булевская формула будет выполнена.

Начнём с того, что нарисуем три попарно соединённые вершины: они гарантированно должны быть раскрашены в разные цвета. Поскольку цвета всё равно можно переставлять — будем считать, что тот цвет, который у левой вершины, это "0", у правой "1", а у оставшейся цвет назовём "база" (ни 0, ни 1).

Теперь для каждой переменной X заведём две вершины, X и ¬X. И соединим их друг с другом и с базой — как раз это гарантирует, что кто-то из X и ¬X будет нулём, а кто-то единицей.

Осталось сделать что-то, раскрашивание чего будет равносильно одной "скобке" X⋁Y⋁Z (где X,Y,Z — переменные или их отрицания). Вот если бы мы нарисовали ещё один треугольник и соединили его вершины с вершинами переменных/отрицаний X, Y и Z — то значения X=Y=Z=0 мы этим бы запретили (потому что из трёх вершин треугольника хоть одна нулём да будет раскрашена). Но вот беда — мы так и X=Y=Z=1 запретим, а этого бы не хотелось!

Не работает. Дорабатывать надо!

Поэтому давайте сделаем так. Будем "подключать" переменные X, Y, Z к этому треугольнику не напрямую, а через дополнительные (специально для этой дизъюнкции выделенные) промежуточные вершины, соединённые ещё и с 1. Тогда если было X=Y=Z=0, то на промежуточных вершинах мы можем поставить только "базу" (потому что они соединены и с 0, и с 1), и продолжить раскраску на треугольник мы не сможем. Наоборот, если какая-то из переменных равна 1, то промежуточную вершину можно раскрасить как "0", и как "базу". И отсюда уже легко увидеть, что мы всегда можем раскрасить промежуточные вершины не все в один цвет — и дальше продлить эту раскраску на треугольник.

А вот так правильно!

Подключая по одному такому "удлинённому треугольнику" на каждую скобку, мы получаем граф, который можно правильно раскрасить в 3 цвета тогда и только тогда, когда есть значения переменных, обращающие булевскую формулу в истину. И вот 3-SAT сведена к 3-COL. Ура!

Так что, чтобы если X хочет нас убедить, что он умеет доказывать гипотезу Римана, не раскрывая доказательство — нужно попросить его записать его формально, в виде алгоритмически-проверяемой последовательности вывода (где каждая следующая строчка получается из предыдущих применением одного из правил вывода). Спрашиваем, какую длину его доказательство занимает (та самая пачка бумаги, которой он потрясает); резервируем под его доказательство ProofText ячейки алгоритма формальной проверки
CheckProof(RiemannHypothesis,ProofText).
Смотрим, сколько времени алгоритм будет работать, превращаем потенциальный протокол работы+"окончание работы с выводом "верно, доказано"" в булевскую формулу для 3-SAT. Переделываем её в граф для 3-COL. Ура — можно применить процедуру проверки!

И в заключение — очень хороший (и совсем о другом) текст А. А. Разборова:
https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/

Берем число A, возводим в степень n, округляем до целого вверх. Бывает ли такое A, что все время (при всех натуральных n) получается число, отличающееся от полного квадрата ровно на 2?

// задача Д.Крекова на ММО сегодня, https://olympiads.mccme.ru/mmo/2021/

(теперь — с правильной ссылкой)

Да, а задача правда красивая!

https://mccme.ru/dubna/2021/

Летняя школа «Современная математика» имени Виталия Арнольда планируется в этом году с 19 по 30 июля в Дубне (в очном формате). Начинается прием заявок от школьников 10 и 11 классов и студентов I и II курсов.

Прекрасное прошлогоднее: самый обычный топологический препринт на arXiv-е: https://arxiv.org/pdf/2003.13758.pdf (картинка — одна страница оттуда).
Rami Luisto, "A non-Euclidean story or: how to persist when your geometry doesn’t."

Статья должна читаться как роман!

https://youtu.be/O85OWBJ2ayo

3blue1brown всегда интересно смотреть,

а отдельно приятно, что «The book shown at the start is Vladimir Arnold's (excellent) textbook on ordinary differential equations» ( https://biblio.mccme.ru/node/6102/ )

Экслюзив: Письмо Рохлина Гудкову о том, что он доказал его гипотезу.

"Без сомнения, это доказательство лучше выражает топологическую суть дела, чем первое. Оно не было найдено сразу просто потому, что общая топологическая теорема, на которой оно основано [т.е. сравнение κ(F)−σ(X) ≡ 2τ(F)mod 8] не была известна. Вероятно, я скоро напишу это доказательство подробно. Конечно, я пришлю его Вам. Не знаю, сможете ли Вы ещё учесть его в Вашем обзоре.

Напишите, пожалуйста, нет ли аналогичных гипотез, относящихся к другим ситуациям, например, к кри- вым нечётной степени, к поверхностям или к неплоским кривым." 21.03.1972.

Подробнее.

Эйлеровой характеристикой многогранника называется число χ=В−Р+Г, где В, Р и Г — количества его вершин, ребер и граней соответственно. Оказывается, эйлерова характеристика зависит лишь от числа «дырок» в многограннике, например для многогранников без дырок (или как говорят математики, односвязных многогранников) эйлерова характеристика равна 2. То есть для куба, тетраэдра, октаэдра и любого другого многогранника без дыр χ=2. А для многогранника с g дырами χ=2−2g. Используя эйлерову характеристику, можно доказать несуществование некоторых многогранников. Например, не существует многогранника без дыр или с одной дыркой, у которого все грани — шестиугольники, попробуйте это проверить самостоятельно. Но если убрать условие на число дырок, то такие многогранники уже можно найти. Гораздо сложнее найти такой многогранник, все грани которого — выпуклые шестиугольники. На сегодняшней картинке изображён один такой многогранник. Попробуйте вычислить число его дырок :)
#рисункиМихаилаПанова
#которисунки
#MetaPost