Математические байки

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

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

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

Берем число A, возводим в степень n, округляем до целого вверх. Бывает ли такое A, что все время (при всех натуральных n) получается число, отличающееся от полного квадрата ровно на 2? // задача Д.Крекова на ММО сегодня, https://olympiads.mccme.ru/mmo/2021/

Берем число A, возводим в степень n, округляем до целого вверх. Бывает ли такое A, что все время (при всех натуральных n) получается число, отличающееся от полного квадрата ровно на 2? // задача Д.Крекова на ММО сегодня, https://mccme.ru/mmo/2021/

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

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

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

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

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

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

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

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

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

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

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

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

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

Давайте я закончу рассказ про 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.