Comments 11
Спасибо, отличная статья, буду рекомендовать ученикам
Утверждения такого вида обобщают математические теоремы, поскольку любая математическая теорема гласит, что утверждение, записанное на формальном языке, принадлежит множеству истинных утверждений.
Возможно имелось в виду множество доказуемых утверждений? Множество истинных утверждений (арифметики Пеано) не перечислимо (Тарский).
Возможно я не совсем понял статью и стоит перечитать еще раз, однако не могли бы вы проиллюстировать утверждение возможности доказательства алиби без его разглашения?
Это хороший вопрос. Я попробую пояснить на примере. Пусть алиби — это распечатка местонахождения телефонного аппарата, которую выдал сотовый оператор. Будем считать, что сотовый оператор выдал эту распечатку в стандартном виде на флешке вместе с электронной подписью корректности этой выписки. Можно написать программу, которая получает на вход ФИО человека и такую распечатку и проверяет, что 1) электронная подпись корректная 2) человек ФИО, действительно, был далеко от места преступления в нужное время. Если проверка проходит, то программа выдает 1, если не проходит по какой-либо причине, то выдает 0. Если программа выдает 1, значит алиби подтверждено. Эту программу судья просит написать независимого программиста и исходные коды этой программы открыты, все могут убедиться, что она делает то, что должна делать. Эта программа задает систему доказательств для множества людей, которые в момент преступления были далеко от места преступления и у них был включен телефон. Нетрудно понять, что такая программа будет работать полиномиальное от длины входа время. А это значит, что множество людей M, невиновность которых можно доказать с помощью этой программы лежит в классе NP. А как я писал в статье, для любого языка из класса NP можно построить интерактивное доказательство с нулевым разглашением.
Могу даже примерно описать, как будет выглядеть это интерактивное доказательство. Во-первых, выбирается конкретный NP-полный язык, для которого удобно строить доказательства с нулевым разглашением. Этот язык 3COL — множество графов, вершины которого можно правильным образом раскрасить в 3 цвета (правильным образом — это когда две вершины, соединенные ребром, покрашены в разные цвета). Доказательством принадлежности этому языку будет сама раскраска. Для этого языка есть доказательство с нулевым разглашением, его я опишу в самом конце. Поскольку 3COL — это NP-полный язык, значит к нему сводится любой другой язык из класса NP, в том числе и язык M. Судья заказывает программисту сведение языка M к языку 3COL, он пишет эту программу и опять же код этой программы любой может проверить. Что делает это сведение? Оно отображает ФИО человека в граф, если человек обладает алиби, то этот граф будет 3-раскрашиваемым, если не обладает, то не будет 3-раскрашиваемым. Также можно написать программу, которая довольно быстро по содержимому флешки выдаст раскраску графа. Эту раскраску обвиняемый не должен никому сообщать, поскольку, возможно, из нее можно извлечь какую-то информацию с флешки.
Теперь как же всем продемонстировать, что граф красится в 3 цвета, не предъявляя раскраску? В зал судебного заседания выносится большой холст, на котором нарисован граф, посчитанный программой. Обвиняемый случайным образом переставляет цвета своей раскраски и пишет в вершине ее цвет вершины, но закрывает вершину тут же сверху фишкой, из под которой не видно, что написано в вершине. После чего предлагает прокурору выбрать любое ребро графа, прокурор выбирает, обвиняемый снимает две фишки под концами этих ребер. Если получились одинаковые цвета, то доказательство ложное, поскольку две вершины, соединенные ребром, должны быть покрашены в один цвет. Теперь допустим, что раскраски не существует, тогда хотя бы одним ребром можно уличить преступника. Если ребер m, то если прокурор будет выбирать ребро случайным образом, то ему повезет с вероятностью 1/m. Значит, надо этот процесс повторить 10m раз. Перед каждым повторением процесса обвиняемый перемешивает случайным образом цвета и меняет пометки вершин. Вероятность того, что все 10m раз преступнику будет везти, не превосходит (1-1/m)10m<e-10.
Могу даже примерно описать, как будет выглядеть это интерактивное доказательство. Во-первых, выбирается конкретный NP-полный язык, для которого удобно строить доказательства с нулевым разглашением. Этот язык 3COL — множество графов, вершины которого можно правильным образом раскрасить в 3 цвета (правильным образом — это когда две вершины, соединенные ребром, покрашены в разные цвета). Доказательством принадлежности этому языку будет сама раскраска. Для этого языка есть доказательство с нулевым разглашением, его я опишу в самом конце. Поскольку 3COL — это NP-полный язык, значит к нему сводится любой другой язык из класса NP, в том числе и язык M. Судья заказывает программисту сведение языка M к языку 3COL, он пишет эту программу и опять же код этой программы любой может проверить. Что делает это сведение? Оно отображает ФИО человека в граф, если человек обладает алиби, то этот граф будет 3-раскрашиваемым, если не обладает, то не будет 3-раскрашиваемым. Также можно написать программу, которая довольно быстро по содержимому флешки выдаст раскраску графа. Эту раскраску обвиняемый не должен никому сообщать, поскольку, возможно, из нее можно извлечь какую-то информацию с флешки.
Теперь как же всем продемонстировать, что граф красится в 3 цвета, не предъявляя раскраску? В зал судебного заседания выносится большой холст, на котором нарисован граф, посчитанный программой. Обвиняемый случайным образом переставляет цвета своей раскраски и пишет в вершине ее цвет вершины, но закрывает вершину тут же сверху фишкой, из под которой не видно, что написано в вершине. После чего предлагает прокурору выбрать любое ребро графа, прокурор выбирает, обвиняемый снимает две фишки под концами этих ребер. Если получились одинаковые цвета, то доказательство ложное, поскольку две вершины, соединенные ребром, должны быть покрашены в один цвет. Теперь допустим, что раскраски не существует, тогда хотя бы одним ребром можно уличить преступника. Если ребер m, то если прокурор будет выбирать ребро случайным образом, то ему повезет с вероятностью 1/m. Значит, надо этот процесс повторить 10m раз. Перед каждым повторением процесса обвиняемый перемешивает случайным образом цвета и меняет пометки вершин. Вероятность того, что все 10m раз преступнику будет везти, не превосходит (1-1/m)10m<e-10.
Оказывается, что это сделать можно с помощью леммы Фаркаша, которая утверждает, что если система нестрогих линейных неравенств несовместна, то можно сложить эти неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Например, система на рисунке несовместна, и если сложить первое уравнение с коэффициентом 1, второе с коэффициентом 2, а третье с коэффициентом 1, то получится 0≥1. Доказательством несовместности будет как раз набор неотрицательных коэффициентов.
Проясните пожалуйста момент. У вас лемма в форме «Если А, то В» (A=>B). Вы находите условия, при которых В, и утверждаете, что тогда А (B=>A). Либо лемма должна быть в форме «А тогда и только тогда, когда B» (A<=>B), либо у вас тут логическая ошибка.
Лемма Фаркаша, конечно, верна в обе стороны: система неравенств несовместна тогда и только тогда, когда можно сложить неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Я сформулировал неочевидную импликацию (которая утверждает, что доказать таким образом всегда можно), в обратную сторону лемма очевидна: если уж вывели противоречие, то понятно, что система несовместна. Но формально вы правы.
Я тут опечаток наловил.
Видимо короткими, а не корректными.
По исправлению этот комментарий можно удалять.
Если мы не ограничиваем размер доказательства, то окажется, что доказательства нужны, а если будем требовать, чтобы доказательства были корректными, то вопрос о нужности доказательств эквивалентен важнейшему открытому вопросу о равенстве классов P и NP.
Видимо короткими, а не корректными.
Н.К. Верещагин, Теоретико-сложностные проблемы крипотграфии, консект лекций
По исправлению этот комментарий можно удалять.
Я бы для интерактивных доказательств привёл другой (или ещё один) житейский пример. Часто на зачёте или экзамене требуется понять понимает ли студент некоторую тему или нет. Но из того потока сознания, который выдаёт студент, понять ничего нельзя, поэтому преподаватель задаёт ему идиотские вопросы, правильные ответы на которые лишь увеличивают вероятность того, что студент действительно понимает тему, однако это ещё не гарантирует, что студент понимает её правильно. Возможно он не понимает её совсем или понимает неправильно, но каким-то чудом из ошибочного понимания умудряется выдавать правильные ответы. А как только студент не ответил на вопрос из которого следует, что он ничего не понял совсем, то преподаватель ставит ему двойку или тройку, после чего студент рассказывает коллегам истории о злом кровожадном преподавателе, который его два часа гонял по теме и в итоге завалил.
Sign up to leave a comment.
«Что такое доказательство?»: взгляд из теоретической информатики