Давайте я закончу рассказ про NP и вокруг того. Мы пока сказали, что такое класс NP.
В начале 1970-х поняли две вещи: во-первых, в классе NP есть "самая сложная задача" — к которой любая другая NP-задача за полиномиальное время сводится. И во-вторых, что таких задач (сводящихся друг к другу) много.

Предъявить одну такую задачу совсем просто: собственно говоря, она практически уже выписана выше. А именно: пусть нам задан алгоритм C и полиномы P_1, P_2.
Q(x)="найдётся ли второй вход S, длины |S|<P_1(|x|), на котором за время не больше P_2(|x|) алгоритм C закончит работу и выдаст "да"? "

Такая задача явно принадлежит классу NP: если S уже задан, то нужно просто "в режиме интерпретатора" сделать P_2(|x|) шагов заданного алгоритма C и проверить, куда мы придём.
И любая NP-задача к ней сводится — для неё C это тот самый её алгоритм Check из определения!
Так что — вот наш первый пример NP-полной задачи.

Из него сразу можно получить ещё один — выполнимость булевской формулы. Допустим, что у нас написана булевская формула из переменных, их отрицаний (¬), конъюнкций (И, ⋀) и дизъюнкций (ИЛИ, ⋁). Можно ли подставить вместо переменных булевские единицы и нули (True и False) так, чтобы вся формула давала единицу?
Очевидно, что эта задача принадлежит классу NP: сертификат это как раз то, что нужно подставить. А почему она NP-полна?

Достаточно к ней свести уже увиденную нами NP-полную задачу, "найдётся ли S длины |S|<P_1(|x|) такой, что C(x,S)="да" за время P_2(|x|)".
Посмотрим на "протокол работы алгоритма C": закодируем нулями и единицами состояние каждой ячейки памяти в каждый момент времени. Тогда то, что набор нулей и единиц корректно кодирует протокол — это большая булевская формула, что в каждый момент времени и в каждой ячейке переход от этого момента времени к следующему выполнен правильно. Начальные условия (где нужно написать, что часть начальных данных это вход x, поставить пишуще-читающую головку машины Тьюринга на исходную позицию и в начальном состоянии, и так далее) и то, что алгоритм заканчивает работу и печатает "да" — это тоже просто требование на часть переменных (подстановка нулей и единиц вместо некоторых из них). И вот и всё сведение!

Более того — такая формула это всегда большая-большая конъюнкция довольно простых выражений "для любого t для любого места m [переход в точке пространства-времени (m,t) выполнен правильно]". Так что даже вопрос про такие формулы уже NP-полон.

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

А это несложно задать конъюнкцией четырёх дизъюнкций: утверждение
"c=f(a,b)"
равносильно тому, что для каждой пары возможных значений a_0, b_0 мы пишем
"(a не равно a_0) ИЛИ (b не равно b_0) ИЛИ (с равно f(a_0,b_0))",
где вместо "переменная равна константе" мы ставим саму переменную, если константа это 1 и её отрицание, если константа это 0. Собственно, И-НЕ таким образом задаётся как "c=И-НЕ (a,b)" <=>
(¬a ИЛИ ¬b ИЛИ ¬c) И
(¬a ИЛИ b ИЛИ c) И
(a ИЛИ ¬b ИЛИ c) И
(a ИЛИ b ИЛИ c);
строчки тут соответствуют наборам входов и значениям 11->0, 10->1, 01->1, 00->1.

Так что NP-полна задача выполнимости булевской формулы, которая есть большая-большая конъюнкция скобок, в каждой из которых дизъюнкция всего-то трёх переменных или их отрицаний. И эта задача называется 3-SAT.

Давайте я чуть-чуть пообсуждаю параллели.
Мы раньше видели многочлен нескольких переменных, все положительные значения которого в неотрицательных целых точках — простые.

Разбираясь в том, как он работает — мы увидели, что все переменные, кроме одной, там как раз служат для кандидата в значение "справкой о простоте" (а если она не проходит проверку, то на этом наборе переменных значение автоматически становится неположительным). Правда, "справка" эта была вовсе не полиномиального размера!

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

Более того — решение десятой проблемы Гильберта как "любое перечислимое множество диофантово" устроено очень похоже на сведение к 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/ )