Если просуммировать такое за все шаги, то получается:
Число пересечений с осью ординат для исходной кривой (которое и есть то, что мы ищем)
минус
число пересечений с осью ординат для последней кривой, к которой мы приходим (а это просто точка (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 )
Давайте я закончу рассказ про 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.