==
Да, ещё одно — как можно реализовать конверты: хэшем. Если есть (объявлена публично) односторонняя функция F (которую трудно обратить, но которая тем не менее взаимно-однозначна), то пусть X на каждом шаге для каждой вершины j вычисляет
f_j=F(c_j R_j),
где с_j — пара бит, кодирущих цвет в этой вершине, а R_j — ещё куча-куча "мусорных бит", и объявляет результат вычисления f_j публично. (Мусор нужен, чтобы Y не мог просто перебрать три варианта цвета и вычислить от них F; если я правильно понимаю, такой мусор в криптографии называется "солью").
И протокол дополняется тем, как происходит "вскрытие конвертов": Y говорит, какие именно конверты вскрывает, X для них объявляет c_j и R_j, после чего Y проверяет, что F от заявленных c_j R_j это действительно ранее объявленные f_j.
А стратегия X — тем, что мусорные биты нужно выбирать совершенно случайными, чтобы объявление f_j и впрямь не приводило ни к какой (значимой) утечке информации.
==
Да, ещё одно — как можно реализовать конверты: хэшем. Если есть (объявлена публично) односторонняя функция F (которую трудно обратить, но которая тем не менее взаимно-однозначна), то пусть X на каждом шаге для каждой вершины j вычисляет
f_j=F(c_j R_j),
где с_j — пара бит, кодирущих цвет в этой вершине, а R_j — ещё куча-куча "мусорных бит", и объявляет результат вычисления f_j публично. (Мусор нужен, чтобы Y не мог просто перебрать три варианта цвета и вычислить от них F; если я правильно понимаю, такой мусор в криптографии называется "солью").
И протокол дополняется тем, как происходит "вскрытие конвертов": Y говорит, какие именно конверты вскрывает, X для них объявляет c_j и R_j, после чего Y проверяет, что F от заявленных c_j R_j это действительно ранее объявленные f_j.
А стратегия X — тем, что мусорные биты нужно выбирать совершенно случайными, чтобы объявление f_j и впрямь не приводило ни к какой (значимой) утечке информации.
==
Математические байки
Сделаем вот что: пусть X выберет случайным образом одну из 6 перестановок цветов (ведь если перекрасить все красные вершины в зелёный, а все зелёные в красный — правильная раскраска останется правильной). И положит у каждой вершины запечатанный конверт с цветом…
Да, я исходно написал 1000N и оценку на вероятность в 10^{-400}, после чего коллеги ехидно сказали, что столь малую вероятность уже писать бессмысленно — её сильно мажорирует шанс на ошибочную операцию в процессоре (и много что ещё). Так что я остановился на добивании вероятности до разумно-очень-малой. 🙂
Математические байки
Один из результатов, который упоминали на церемонии вручения премии Абеля — это Zero Knowledge Proof, доказательство с нулевым разглашением. И это действительно очень красивая идея (восходящая к работе Goldreich-Micali-Rackoff, "The Knowledge Complexity of…
И я обещал рассказать про то, что такое NP-задачи.
Определение NP-задачи такое: задача Q относится к классу NP, если
1) Она требует ответа вида Q(x)="да/нет" в зависимости от параметра x
и
2) Ответ "да" может быть доказан некоторой "справкой", проверяемой за полиномиальное время. Формально — существует такой алгоритм Check(x,S), "проверяющий" за полиномиальное по длине входа x время полиномиальный по длине входа x сертификат S:
- для любого x, для которого Q(x)="да", существует S, такой, что Check(x,S)="да";
- ни для одного x, для которого Q(x)="нет", не существует такого S, чтобы Check(x,S)="да"
(плюс ограничения на длину S и на время работы Check).
Стоит отметить, что постановка тут несимметрична по "да/нет": если вопрос Q="x верблюд?" принадлежит классу NP, ибо взятая в зоопарке справка S проверяется процедурой
Check(x,S)="проверить бланк справки, печать зоопарка и совпадение указанного там животного с x"
(при том, что предъявление S="мятая салфетка" не означает, что x не верблюд — а только то, что данная S этого не доказывает),
то где брать справку, что ты не верблюд, совершенно непонятно.
Менее абстрактный пример — вопрос о том, является ли данное натуральное число N составным, принадлежит классу NP. "Справкой" будет его разложение на два сомножителя, S=(a,b); процедура проверки —
Check(N,S)=
- проверить, что S=(a,b), где a,b натуральные и больше 1 (а то норовят всякие подсунуть строку вместо числа на вход).
- проверить, что N=ab.
(Последнее даже при выполнении умножения "в столбик" требует ~n^2 операций, где n — число цифр в записи N)
А вот принадлежность вопроса "является ли N простым" классу NP совершенно неочевидна. Потому что проверка "в лоб" подразумевала бы перебор делителей от 1 до корня из N — и это даже для N порядка 10^100 ну совершенно нереалистично. А как бы могла быть устроена короткая и быстро проверяемая "справка о простоте" — на вид непонятно.
(На самом деле, этот вопрос даже классу P принадлежит — но без дополнительных предположений это результат начала 2000-х: см. Agrawal, Kayal, Saxena, PRIMES in P, Annals of Mathematics, 2004 + https://en.wikipedia.org/wiki/AKS_primality_test )
Определение NP-задачи такое: задача Q относится к классу NP, если
1) Она требует ответа вида Q(x)="да/нет" в зависимости от параметра x
и
2) Ответ "да" может быть доказан некоторой "справкой", проверяемой за полиномиальное время. Формально — существует такой алгоритм Check(x,S), "проверяющий" за полиномиальное по длине входа x время полиномиальный по длине входа x сертификат S:
- для любого x, для которого Q(x)="да", существует S, такой, что Check(x,S)="да";
- ни для одного x, для которого Q(x)="нет", не существует такого S, чтобы Check(x,S)="да"
(плюс ограничения на длину S и на время работы Check).
Стоит отметить, что постановка тут несимметрична по "да/нет": если вопрос Q="x верблюд?" принадлежит классу NP, ибо взятая в зоопарке справка S проверяется процедурой
Check(x,S)="проверить бланк справки, печать зоопарка и совпадение указанного там животного с x"
(при том, что предъявление S="мятая салфетка" не означает, что x не верблюд — а только то, что данная S этого не доказывает),
то где брать справку, что ты не верблюд, совершенно непонятно.
Менее абстрактный пример — вопрос о том, является ли данное натуральное число N составным, принадлежит классу NP. "Справкой" будет его разложение на два сомножителя, S=(a,b); процедура проверки —
Check(N,S)=
- проверить, что S=(a,b), где a,b натуральные и больше 1 (а то норовят всякие подсунуть строку вместо числа на вход).
- проверить, что N=ab.
(Последнее даже при выполнении умножения "в столбик" требует ~n^2 операций, где n — число цифр в записи N)
А вот принадлежность вопроса "является ли N простым" классу NP совершенно неочевидна. Потому что проверка "в лоб" подразумевала бы перебор делителей от 1 до корня из N — и это даже для N порядка 10^100 ну совершенно нереалистично. А как бы могла быть устроена короткая и быстро проверяемая "справка о простоте" — на вид непонятно.
(На самом деле, этот вопрос даже классу P принадлежит — но без дополнительных предположений это результат начала 2000-х: см. Agrawal, Kayal, Saxena, PRIMES in P, Annals of Mathematics, 2004 + https://en.wikipedia.org/wiki/AKS_primality_test )
Давайте я закончу рассказ про 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.
В начале 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.
Математические байки
И вот на картинке выше явный пример такого многочлена — которому посвящена статья James P. Jones, Daihachiro Sato, Hideo Wada and Douglas Wiens, "Diophantine Representation of the Set of Prime Numbers", The American Mathematical Monthly, 83 :6 (1976), pp.…
Давайте я чуть-чуть пообсуждаю параллели.
Мы раньше видели многочлен нескольких переменных, все положительные значения которого в неотрицательных целых точках — простые.
Мы раньше видели многочлен нескольких переменных, все положительные значения которого в неотрицательных целых точках — простые.
Математические байки
Photo
Разбираясь в том, как он работает — мы увидели, что все переменные, кроме одной, там как раз служат для кандидата в значение "справкой о простоте" (а если она не проходит проверку, то на этом наборе переменных значение автоматически становится неположительным). Правда, "справка" эта была вовсе не полиномиального размера!
Математические байки
И если это всё сделать — мы получим систему экспоненциально-полиномиальных уравнений, таких, что для p найдутся все остальные (неотрицательные целые) переменные тогда и только тогда, когда p простое. Ура! Собственно, мой рассказ выше это пересказ [части]…
И аккуратно разобрали более простые версии — сначала, как можно устроить справку, проверяемую с помощью факториала, а потом научились строить проверяющий для числа некоторую "справку о простоте" экспоненциально-полиномиальный многочлен.
Математические байки
Возвращаясь к диофантовости всех перечислимых множеств — собственно говоря, идея "сертификата" работает и тут. А именно — представим себе, что какая-то машина долго-долго работала и наконец закончила работу. Давайте соберём все состояния её "регистров" во…
Более того — решение десятой проблемы Гильберта как "любое перечислимое множество диофантово" устроено очень похоже на сведение к 3-SAT: чтобы нас убедить, что алгоритм -- машина Тьюринга, или, лучше, машина со счётчиками -- на данном входе хоть когда-нибудь останавливается, он приходит со справкой-сертификатом-протоколом своего выполнения, где (помимо всего прочего) записаны (в системе счисления с огромным основанием, "чтобы влезло") все состояния во все моменты времени. А многочлен проверяет, что все переходы действительно сделаны правильно (и для этого нужны ещё дополнительные переменные — они работают "справкой", удостоверяющей, что протокол-справка заполнен правильно).
===
Вернёмся теперь к тому, с чего мы начинали: к задаче о существовании у данного графа правильной трёхцветной раскраски — 3-COL. И поймём, что она тоже NP-полна.
Опять же, понятно, что это NP-задача — остаётся к ней любую из NP-полных задач свести. И конечно, сводить нужно 3-SAT — рисуя такой граф, чтобы его правильная раскраска соответствовала набору значений переменных, на котором булевская формула будет выполнена.
Начнём с того, что нарисуем три попарно соединённые вершины: они гарантированно должны быть раскрашены в разные цвета. Поскольку цвета всё равно можно переставлять — будем считать, что тот цвет, который у левой вершины, это "0", у правой "1", а у оставшейся цвет назовём "база" (ни 0, ни 1).
Вернёмся теперь к тому, с чего мы начинали: к задаче о существовании у данного графа правильной трёхцветной раскраски — 3-COL. И поймём, что она тоже NP-полна.
Опять же, понятно, что это NP-задача — остаётся к ней любую из NP-полных задач свести. И конечно, сводить нужно 3-SAT — рисуя такой граф, чтобы его правильная раскраска соответствовала набору значений переменных, на котором булевская формула будет выполнена.
Начнём с того, что нарисуем три попарно соединённые вершины: они гарантированно должны быть раскрашены в разные цвета. Поскольку цвета всё равно можно переставлять — будем считать, что тот цвет, который у левой вершины, это "0", у правой "1", а у оставшейся цвет назовём "база" (ни 0, ни 1).
Осталось сделать что-то, раскрашивание чего будет равносильно одной "скобке" 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. Ура!
Математические байки
Один из результатов, который упоминали на церемонии вручения премии Абеля — это Zero Knowledge Proof, доказательство с нулевым разглашением. И это действительно очень красивая идея (восходящая к работе Goldreich-Micali-Rackoff, "The Knowledge Complexity of…
Так что, чтобы если X хочет нас убедить, что он умеет доказывать гипотезу Римана, не раскрывая доказательство — нужно попросить его записать его формально, в виде алгоритмически-проверяемой последовательности вывода (где каждая следующая строчка получается из предыдущих применением одного из правил вывода). Спрашиваем, какую длину его доказательство занимает (та самая пачка бумаги, которой он потрясает); резервируем под его доказательство ProofText ячейки алгоритма формальной проверки
CheckProof(RiemannHypothesis,ProofText).
Смотрим, сколько времени алгоритм будет работать, превращаем потенциальный протокол работы+"окончание работы с выводом "верно, доказано"" в булевскую формулу для 3-SAT. Переделываем её в граф для 3-COL. Ура — можно применить процедуру проверки!
CheckProof(RiemannHypothesis,ProofText).
Смотрим, сколько времени алгоритм будет работать, превращаем потенциальный протокол работы+"окончание работы с выводом "верно, доказано"" в булевскую формулу для 3-SAT. Переделываем её в граф для 3-COL. Ура — можно применить процедуру проверки!
Wikipedia
Правило вывода
правило перехода от посылок к заключению
И в заключение — очень хороший (и совсем о другом) текст А. А. Разборова:
https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/
https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/
Forwarded from Непрерывное математическое образование
Берем число A, возводим в степень n, округляем до целого вверх. Бывает ли такое A, что все время (при всех натуральных n) получается число, отличающееся от полного квадрата ровно на 2?
// задача Д.Крекова на ММО сегодня, https://olympiads.mccme.ru/mmo/2021/
// задача Д.Крекова на ММО сегодня, https://olympiads.mccme.ru/mmo/2021/