А если атлет начинал и закончил путь на разных дугах — то если добавить к пути замыкание "в положительном направлении", после которого суммы у арбитров совпадут, то один из двух арбитров его увидит, а другой нет. И уже совсем легко увидеть, что общий ответ такой:
число пересечений (с учётом знака) для арбитра A1 минус
число пересечений (с учётом знака) для арбитра А2 =
F(начала пути)-F(конца пути),
где F это 1, если мы начали на дуге от A2 к A1 (обозначенной тут +-), и 0 иначе.
число пересечений (с учётом знака) для арбитра A1 минус
число пересечений (с учётом знака) для арбитра А2 =
F(начала пути)-F(конца пути),
где F это 1, если мы начали на дуге от A2 к A1 (обозначенной тут +-), и 0 иначе.
Если просуммировать такое за все шаги, то получается:
Число пересечений с осью ординат для исходной кривой (которое и есть то, что мы ищем)
минус
число пересечений с осью ординат для последней кривой, к которой мы приходим (а это просто точка (1,0), которая стоит на месте и ось ординат не пересекает)
равно
сумме по всем шагам разностей F(начало пути) минус F(конца пути), где F смотрит, есть ли между P_j и P_{j+1} перемена знака.
Потому что арбитры в нашем случае это ось ординат (до поворота) и ось абсцисс (после), и вот дуга между ними это и есть "координаты разного знака".
Ну а сумма разностей это разность сумм, и каждая из сумм это и есть общее число перемен знака в последовательности!
Число пересечений с осью ординат для исходной кривой (которое и есть то, что мы ищем)
минус
число пересечений с осью ординат для последней кривой, к которой мы приходим (а это просто точка (1,0), которая стоит на месте и ось ординат не пересекает)
равно
сумме по всем шагам разностей F(начало пути) минус F(конца пути), где F смотрит, есть ли между P_j и P_{j+1} перемена знака.
Потому что арбитры в нашем случае это ось ординат (до поворота) и ось абсцисс (после), и вот дуга между ними это и есть "координаты разного знака".
Ну а сумма разностей это разность сумм, и каждая из сумм это и есть общее число перемен знака в последовательности!
Ура, победа! Мы связали топологический взгляд с классической формулировкой теоремы Штурма через число перемен знака.
Ещё — пара картинок из "Геометрии дискриминанта" В. А. Васильева:
Топологическая степень это ответ на вопрос, почему в множестве пар многочленов (ровно) второй степени без общих корней нельзя пройти от пары "корни чередуются" к паре "корни не чередуются" (и кстати, нельзя поменять порядок чередования корней). Ибо при одном чередовании будет обход по часовой стрелке, при другом против, а при отсутствии чередования степень нулевая.
Математические байки
Photo
А вот — страница из текста Д. В. Аносова 2003 года; как раз очень близко к тому, что мы уже видели раньше, только у него цепная дробь обычная, поэтому в ответе возникает чередование знаков:
Ну а часть рассказа выше (подход через степени) вошла в (онлайн)-курс топологии, который мы с коллегами ведём — собственно, уже заканчиваем — для первого курса Вышки. Кто же знал, когда всё это только задумывалось, что курс с частичным онлайном и красивыми картинками вынужденно превратится в полный онлайн...
From behind the stages:
From behind the stages:
Через пару минут начнётся объявление премии Абеля:
https://www.youtube.com/watch?v=0_NK_OkpmUY
https://www.youtube.com/watch?v=0_NK_OkpmUY
YouTube
The Abel Prize announcement 2021 - Avi Wigderson and László Lovász
0:49 The Abel Prize announced by Hans Petter Graver, President of The Norwegian Academy of Science and Letters
1:38 Citation by Hans Munthe-Kaas, Chair of the Abel committee
10:22 Popular presentation of the prize winners work by Alex Bellos, British writer…
1:38 Citation by Hans Munthe-Kaas, Chair of the Abel committee
10:22 Popular presentation of the prize winners work by Alex Bellos, British writer…
Forwarded from Непрерывное математическое образование
Abel Prize 2021:
László Lovász & Avi Wigderson
“for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”
László Lovász & Avi Wigderson
“for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”
Forwarded from Непрерывное математическое образование
Математические байки
Через пару минут начнётся объявление премии Абеля: https://www.youtube.com/watch?v=0_NK_OkpmUY
Один из результатов, который упоминали на церемонии вручения премии Абеля — это Zero Knowledge Proof, доказательство с нулевым разглашением. И это действительно очень красивая идея (восходящая к работе Goldreich-Micali-Rackoff, "The Knowledge Complexity of Interactive Proof-Systems").
Как мне это когда-то рассказывали — вот представьте себе, что математик X доказал гипотезу Римана. Естественно было бы написать статью или рассказать результат на семинаре — но X опасается, что его результат украдут. Может ли X убедить коллег, что у него действительно есть доказательство — не рассказав его? И оказывается, что да, есть способ это сделать — о доказательстве вообще ничего не рассказав, кроме его длины. (Можно считать, что X потрясает пачкой бумаги со словами, "этого хватит, чтобы доказательство записать".)
Более того, — это возможно для вообще любой NP-задачи. И вот тут алгоритм придумали Oded Goldreich, Silvio Micali и Avi Wigderson: см. "How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design" (1986; https://link.springer.com/content/pdf/10.1007%2F3-540-47721-7_11.pdf )
В двух словах (я уточню ближе к концу этого рассказа) — нас интересуют ситуации, когда уже предъявленный ответ можно быстро проверить, но вот сам поиск этого ответа, возможно, безумно сложен. Например, если Вася хочет доказать, что он знает гамильтонов (посещающего каждую вершину ровно один раз) путь в графе. Как раз — проверить, что путь по 1000 вершин графа действительно проходит через каждую вершину, ровно один раз, и каждый раз переходит по ребру — легко. А вот найти такой путь (если он есть) для заданного графа — слоожно...
Тот пример, из которого всё выводится в работе Goldreich, Micali, Wigderson — это задача трёхцветной раскраски: раскрасить вершины графа в 3 цвета так, чтобы соседние вершины были бы раскрашены в разные цвета.
(Кстати: если граф планарный, то в четыре цвета его вершины правильным образом раскрасить всегда можно — и это и утверждает теорема о четырёх красках.)
Понятно, что это задача как раз такого класса: найти раскраску может быть очень сложно — но вот когда раскраска уже предъявлена, проверить, что это действительно правильная раскраска, занимает вполне разумное время.
Так вот — допустим, что X знает правильную трёхцветную раскраску данного графа. Как ему убедить в этом Y, не раскрывая никакой информации?
Как мне это когда-то рассказывали — вот представьте себе, что математик X доказал гипотезу Римана. Естественно было бы написать статью или рассказать результат на семинаре — но X опасается, что его результат украдут. Может ли X убедить коллег, что у него действительно есть доказательство — не рассказав его? И оказывается, что да, есть способ это сделать — о доказательстве вообще ничего не рассказав, кроме его длины. (Можно считать, что X потрясает пачкой бумаги со словами, "этого хватит, чтобы доказательство записать".)
Более того, — это возможно для вообще любой NP-задачи. И вот тут алгоритм придумали Oded Goldreich, Silvio Micali и Avi Wigderson: см. "How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design" (1986; https://link.springer.com/content/pdf/10.1007%2F3-540-47721-7_11.pdf )
В двух словах (я уточню ближе к концу этого рассказа) — нас интересуют ситуации, когда уже предъявленный ответ можно быстро проверить, но вот сам поиск этого ответа, возможно, безумно сложен. Например, если Вася хочет доказать, что он знает гамильтонов (посещающего каждую вершину ровно один раз) путь в графе. Как раз — проверить, что путь по 1000 вершин графа действительно проходит через каждую вершину, ровно один раз, и каждый раз переходит по ребру — легко. А вот найти такой путь (если он есть) для заданного графа — слоожно...
Тот пример, из которого всё выводится в работе Goldreich, Micali, Wigderson — это задача трёхцветной раскраски: раскрасить вершины графа в 3 цвета так, чтобы соседние вершины были бы раскрашены в разные цвета.
(Кстати: если граф планарный, то в четыре цвета его вершины правильным образом раскрасить всегда можно — и это и утверждает теорема о четырёх красках.)
Понятно, что это задача как раз такого класса: найти раскраску может быть очень сложно — но вот когда раскраска уже предъявлена, проверить, что это действительно правильная раскраска, занимает вполне разумное время.
Так вот — допустим, что X знает правильную трёхцветную раскраску данного графа. Как ему убедить в этом Y, не раскрывая никакой информации?
Сделаем вот что: пусть X выберет случайным образом одну из 6 перестановок цветов (ведь если перекрасить все красные вершины в зелёный, а все зелёные в красный — правильная раскраска останется правильной). И положит у каждой вершины запечатанный конверт с цветом получившейся правильной раскраски.
Теперь проверяющий Y выберет две соседние вершины. И вскроет соответствующие им конверты (все остальные конверты немедленно сжигаются).
Дальше может быть одно из двух:
1) Если Y обнаружил совпадающие цвета, то он говорит X "ах ты нехороший человек, обмануть хотел? Не прокатило!". На этом протокол прекращается, а X объявляется жуликом.
2) Если цвета разные, то процедура повторяется. X выбирает новую случайную перестановку, раскладывает конверты, Y выбирает две соседние вершины, вскрывает конверты в них, и так далее.
При этом — если X играет честно и выбирает каждый раз равномерно случайную перестановку, то никакой информации о раскраске (кроме того, что она, похоже, правильная) Y не получает: любая пара соседних вершин может быть равновероятно окрашена любым из 6 способов.
Наоборот, если Y выбирает проверяемое ребро случайным образом, то шанс поймать X, если он жульничает — по меньшей мере 1/N, где N — число рёбер в графе. За 100N раундов шанс, что на самом деле не знающий раскраски обманщик не будет пойман, становится меньше
(1- 1/N)^{100N} ~ e^{-100} < 10^{-40}.
(Ну и, естественно, такая вероятность может быть сделана сколь угодно малой, если 10^{-40} нам почему-то недостаточно.)
Теперь проверяющий Y выберет две соседние вершины. И вскроет соответствующие им конверты (все остальные конверты немедленно сжигаются).
Дальше может быть одно из двух:
1) Если Y обнаружил совпадающие цвета, то он говорит X "ах ты нехороший человек, обмануть хотел? Не прокатило!". На этом протокол прекращается, а X объявляется жуликом.
2) Если цвета разные, то процедура повторяется. X выбирает новую случайную перестановку, раскладывает конверты, Y выбирает две соседние вершины, вскрывает конверты в них, и так далее.
При этом — если X играет честно и выбирает каждый раз равномерно случайную перестановку, то никакой информации о раскраске (кроме того, что она, похоже, правильная) Y не получает: любая пара соседних вершин может быть равновероятно окрашена любым из 6 способов.
Наоборот, если Y выбирает проверяемое ребро случайным образом, то шанс поймать X, если он жульничает — по меньшей мере 1/N, где N — число рёбер в графе. За 100N раундов шанс, что на самом деле не знающий раскраски обманщик не будет пойман, становится меньше
(1- 1/N)^{100N} ~ e^{-100} < 10^{-40}.
(Ну и, естественно, такая вероятность может быть сделана сколь угодно малой, если 10^{-40} нам почему-то недостаточно.)
Математические байки
Сделаем вот что: пусть X выберет случайным образом одну из 6 перестановок цветов (ведь если перекрасить все красные вершины в зелёный, а все зелёные в красный — правильная раскраска останется правильной). И положит у каждой вершины запечатанный конверт с цветом…
==
Вообще-то говоря, я тут смешал в одно описание ("что будет происходить") две вещи: протокол и стратегию игроков . Если их разделять — а это правильно сделать — то протокол состоит в том, что на каждой итерации X кладёт конверты, а Y выбирает из них два, отвечающих соседним вершинам, после чего они вскрываются. И если обнаруживают два одинаковых цвета, то X проиграл, а если за данное большое число раундов X не пойман, то считается, что он Y убедил.
А дальше — честный X с помощью стратегии случайной перестановки цветов на каждом шаге гарантирует, что информация не утечёт при любых действиях Y (какое бы ребро Y ни выбрал, он получает просто равновероятную пару цветов).
Наоборот, честный Y с помощью стратегии случайного выбора ребра на каждом шаге гарантирует, что вероятность для жулика-X проскочить не больше, чем 10^{-40} (и вообще экспоненциально мала по количеству итераций протокола).
А вообще протоколы, стратегии и атаки на протоколы — это большая тонкая наука (и туда мы сейчас точно не пойдём 🙂 ).
==
Вообще-то говоря, я тут смешал в одно описание ("что будет происходить") две вещи: протокол и стратегию игроков . Если их разделять — а это правильно сделать — то протокол состоит в том, что на каждой итерации X кладёт конверты, а Y выбирает из них два, отвечающих соседним вершинам, после чего они вскрываются. И если обнаруживают два одинаковых цвета, то X проиграл, а если за данное большое число раундов X не пойман, то считается, что он Y убедил.
А дальше — честный X с помощью стратегии случайной перестановки цветов на каждом шаге гарантирует, что информация не утечёт при любых действиях Y (какое бы ребро Y ни выбрал, он получает просто равновероятную пару цветов).
Наоборот, честный Y с помощью стратегии случайного выбора ребра на каждом шаге гарантирует, что вероятность для жулика-X проскочить не больше, чем 10^{-40} (и вообще экспоненциально мала по количеству итераций протокола).
А вообще протоколы, стратегии и атаки на протоколы — это большая тонкая наука (и туда мы сейчас точно не пойдём 🙂 ).
==
Вот тут есть демонстрация этого алгоритма со стороны проверяющего:
http://web.mit.edu/~ezyang/Public/graph/noscript.html
Там предлагают выбрать граф — и в одном из случаев к нам пришёл человек с честной раскраской, а в другом нас пытаются обмануть. Confidence внизу отвечает за оценку на "1 минус вероятность того, что обманщику столько раундов подряд бы везло".
http://web.mit.edu/~ezyang/Public/graph/noscript.html
Там предлагают выбрать граф — и в одном из случаев к нам пришёл человек с честной раскраской, а в другом нас пытаются обмануть. Confidence внизу отвечает за оценку на "1 минус вероятность того, что обманщику столько раундов подряд бы везло".
==
Да, ещё одно — как можно реализовать конверты: хэшем. Если есть (объявлена публично) односторонняя функция 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 )