Новая заявка на решение задачи P vs. NP

    На днях Норберт Блюм опубликовал на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия, за которую кроме почестей полагается 1 миллион долларов. В данной статье я собрал небольшое резюме об этом.

    Что доказывается?


    Проблему равенства классов P и NP можно неформально определить следующим образом:
    Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти? Задачи первого типа относятся к классу P, второго — к классу NP. Проблема равенства этих классов является одной из важнейших проблем теории алгоритмов. (Wikipedia)
    В статье Блюма доказывается более сильное утверждение:
    Для задачи проверки, есть ли в графе клика (полный подграф) заданного размера, не существует булевых схем (булевых сетей) полиномиального размера.
    Из этого утверждения следует, что P ≠ NP. Действительно, если P = NP, то для каждой задачи из NP (в т.ч. и для проверки клики) существует полиномиальный алгоритм, а полиномиальный алгоритм можно преобразовать в семейство булевых схем полиномиального размера. Таким образом, если для какой-то задачи из NP не существует булевых схем полиномиального размера, то P ≠ NP.

    Почему сам факт появления доказательства не удивителен


    Как и для любой другой известной математической проблемы, доказательства P = NP или P ≠ NP появляются с завидной регулярностью — можете посмотреть подборку из 100+ доказательств на этом сайте. Однако далеко не все из них привлекают внимание научного сообщества. В предыдущий раз такое случалось 7 лет назад, когда свое доказательство опубликовал Винай Деолаликар, но и в его доказательстве обнаружили ошибку.

    Почему же доказательство Блюма привлекло внимание?


    Во-первых, Норберт Блюм — известный и уважаемый учёный, который в то же время славится своей дотошностью. Сомнительно, что он стал бы публиковать эту статью, если бы не был уверен на 100% в её правильности. Во-вторых, предложенная техника обходит все известные ограничения на доказательство P ≠ NP. Дело в том, что в теории сложности есть серия утверждений вида «такая техника не сможет доказать P ≠ NP» (Natural Proofs, релятивизация, алгебраизация), но предложенная техника аккуратно обходит все эти ограничения.

    Единственный на данный момент серьёзный аргумент против этого доказательства заключается в том, что эта статья выглядит слишком простой для такого результата. Удивительно, что в статье на 30 с небольшим страниц разрешена такая сложная проблема. Действительно, по сравнению с доказательствами Уайлса (Большая теорема Ферма), Перельмана (гипотеза Пуанкаре) и даже с недавним результатом Бабая (квазиполиномиальный алгоритм для изоморфизма графов), доказательство Блюма выглядит невероятно простым и коротким. С другой стороны, у этого может быть объяснение — Блюм не доказывает с нуля, а развивает технику Берга и Ульфберга, которая в свою очередь основана на прорывных результатах Разборова, Андреева и Тардош, то есть может оказаться, что «всё сложное» уже было сделано раньше, и оставалось только «сложить паззл».

    Что теперь будет?


    Ничего особенного. Скорей всего через некоторое время в статье найдут ошибку, как это случалось во всех предыдущих случаях. При этом не исключено (но очень маловероятно), что Блюм действительно доказал, что P ≠ NP. В таком случае на проверку статьи уйдёт довольно много времени — статья не будет признана верной, пока эксперты в этой области не разберут весь результат по кирпичикам и не проверят его правильность досконально.

    Текущее положение дел


    Основное обсуждение происходит на StackExchange — там собираются все комментарии и определяются места, в которых могут быть ошибки. Есть так же тред на Quora и некоторое обсуждение в комментариях к посту Луки Тревиссана.

    Если вы хотите более подробно разобраться в том, что происходит, то почитайте посты Луки Тревиссана и Ричарда Липтона.

    Объяснение от «не специалиста» можно найти тут.

    Пока большинство экспертов настроенны скептично. Например, известный эксперт по сложности и квантовым вычислениям Скотт Ааронсон поставил бы $200 тыс. на то, что доказательство не верно. Кстати, у Скотта Ааронсона есть интереснейший набор из 10 тестов, которые позволяют определить, заслуживает ли статья с решением какой-то серьёзной проблемы, внимания. Насколько я понимаю, статья Блюма проходит все эти тесты, кроме последнего: предложенное доказательство выглядит слишком простым.

    Update: Пока я писал этот пост, в обсуждении на StackExchange появился комментарий, в котором утверждается, что Александр Разборов (на результатах которого строится доказательство Блюма) уже просмотрел статью и нашёл причину, почему это доказательство должно быть ошибочным.

    Update 2: Появилось описание ошибки, которая вероятно является фатальной для доказательства.
    СПБАУ 64,77
    Компания
    Поделиться публикацией
    Комментарии 76
    • НЛО прилетело и опубликовало эту надпись здесь
      • +3
        Интуиция? Или есть более строгое докозательство сего утверждения? Интересно…
        • +2
          Если бы это было алгоритмически доказуемо, то наверное было бы P==NP. Опять-таки интуиция. Но тут вполне возможно что-то связанное с парадоксами и неполнотой формальных систем.
          • 0
            Интуитивно наоборот же, P != NP. Вы же не сможете решить, например, шахматы, не перебирая экспоненциальное число позиций в зависимости от глубины
            • +6
              Шахматы — это плохой пример, т.к. это конечная игра, которая описывается деревом глубины 50, т.е. поиск оптимальной стратегии не просто лежит в P, а решается за константу.

              Думаю, что под словами «алгоритмически доказуемо» выше понимается «доказательство предъявлением алгоритма». И тогда понятно, что таким образом значительно «проще» доказать P = NP (например, предъявить полиномиальный алгоритм для NP-полной задачи), чем доказать, что такого алгоритма не существует (непонятно, какой алгоритм для этого нужно предъявить).
              • 0
                Т.е. построить конструктивное доказательство P != NP не возможно?
                • +4
                  Я этого не утверждал, а лишь попытался угадать мотивацию из комментария выше. Сейчас очень популярны результаты, которые связывают верхние оценки (эффективные алгоритмы) и нижние оценки (отсутствие эффективных алгоритмов). Наиболее известен результат Раена Вильямса о том, что класс NEXP не лежит в классе ACC. Вильямс доказывает, что для некоторой сложной задачи есть алгоритм более эффективный, чем перебор, и из этого следует, что NEXP не лежит в ACC. То есть такое доказательство теоретически возможно.
                  • 0
                    Почему же? Насколько я понял, доказательство в статье как раз конструктивное: приводится контрпример, задача из NP, для которой нет полиномиального алгоритма.
                  • 0
                    Хорошо, вот вам масштабируемая задача: определить точное значение коми (преимущество делающего первый ход игрока) для игры Го на доске размера NxN, как функция от параметра N.
                    • +1
                      Посмотрите комментарий, на который я отвечал. Там шахматы приводились как пример, где интуитивно понятно, что потребуется экспоненциальный перебор. На что я заметил, что это плохой пример и объяснил почему.

                      Ваш пример, ИМХО, тоже плохой. Во-первых, задача менее понятная, т.к. требует знание правил Го и соответственной интуиции в Го. Во-вторых, мне вот совсем не _интуитивно понятно_, что задача, которую Вы преложили — это задача, которая может быть решена только экспоненциальным перебором (даже если это действительно так, хотя без исследования этого вопроса у меня есть большие сомнения).
                      • +1

                        И как решение этой задачи планируется проверять за полиноминальное время? Мне вот почему-то кажется, что эта задача в класс NP не попадает.

                        • 0
                          Я думаю, что она PSPACE как и шахматы. Сказать, попадает в NP или нет, пока не можем (но вряд ли, конечно).
                    • 0
                      Я и не спорю. Но в предыдущем комментарии я предположил несколько другое.
              • +3
                Например, известный эксперт по сложности и квантовым вычисленим Скотт Ааронсон поставил $200 тыс. на то, что доказательство не верно.
                Не совсем, он пишет «я поставил бы, как в прошлый раз...». Он уже один раз отредактировал свой блог, убрав ссылку на неверное сообщение об ошибке, Любош Мотль по этому поводу ещё позлобствовал.
                • +2
                  Вы правы, спасибо, пропустил «бы»! Поправил в статье. Комментарий Мотля забавный =)
              • 0
                Предыдущие 116 «доказательств»: www.win.tue.nl/~gwoegi/P-versus-NP.htm
                • +1
                  Эта ссылка есть в посте, спасибо. В посте также объясняется, чем это доказательство отличается от других.
                  • +1
                    Извиняюсь, ссылку пропустил…

                    Но на счет «чем-то» отличается, у меня достаточно много скептицизма тут.
                    Аппеляция к личности автора, к сожалению, вряд ли можно считать за существенное отличие. Ну а в плане техники… все-таки, глобально, это всего лишь «еще одно доказательство в списке». Потому что у всех 116 тоже есть что-то отличное в технике.

                    Думаю, поднимать хайп пока еще очень и очень рано.
                    • +1
                      Но на счет «чем-то» отличается, у меня достаточно много скептицизма тут.

                      И не у вас одного. Однако более 50-ти доказательств, появившиеся после доказательства Деолаликара 2010 года, прошли незамеченными. В то время как доказательство Блюма привлекло пристальное внимание комьюнити и о нём уже написала значительная часть блоггеров-экспертов по теории сложности.

                      Думаю, поднимать хайп пока еще очень и очень рано.

                      Не спорю. Как я уже написал, скорей всего ошибку найдут довольно быстро. Тем более, что появился комментарий от Разборова, который вроде как объясняет, почему в доказательстве должна быть ошибка (хотя саму ошибку пока никто не нашёл).
                • 0
                  Я наверное ошибаюсь, но разве уже не доказали, что это в принципе недоказуемо?
                  • +5
                    Насколько мне известно, нет, не доказали.
                  • +1
                    Как указано в 1-ом ответе на stackexchange, Alexander Razborov полагает что это доказательство Блюма не верно, и что в 6 теореме доказательства есть ошибка
                    • +1
                      Об этом написано в последнем абзаце поста.
                    • –2
                      Update: Пока я писал этот пост,

                      Пока один пишет статью на хабр, а другой этот бессмысленный коммент к статье, кто-то успевает решать и опровергать решение задач тысячелетия. Дорогая редакция, пристрели мне карму, может тогда тоже сделаю что-то полезное.
                      • +4
                        Чо тут доказывать
                        P=np только когда n=1
                        Во всех остальных случаях не равно
                        Як диты
                      • +2
                        Разборов у нас вёл просеминар по математической логике для студентов первого курса в 1987 году. Он сам тогда только закончил МГУ. Разборов, Шень и Верещагин, втроём.
                        • +4

                          Спасибо, что держите нас в курсе последних новостей.

                        • 0
                          Почему это важная задача? Что изменится, когда будет доказано равенство либо неравенство этих классов? Особенно неравенство. Интуитивно кажется, что они не могут быть равны, но могу также поверить, что они могут быть эквивалентны, но у алгоритмов решения полной задачи за линейное время такая вычислительная сложность каждого шага, что практически такой алгоритм ни для чего не годится.
                          • 0
                            Большинство прикладных задач лежат в классе NP, но далеко не для всех из них существуют эффективные алгоритмы. Вопрос о равенстве классов P и NP, это вопрос о том, есть ли надежда научиться решать эти задачи эффективно или нет. Без разрешения этого вопроса, например, неизвестно, существует ли криптографически стойкие шифры (если P=NP, то односторонних функций нет, а следовательно нет и стойких шифров).
                            Как будет устроен мир при различных исходах хорошо описано в статье Рассела Импальяццо, перевод которой есть на хабре: habrahabr.ru/post/132127
                            • 0
                              Доказать существование некоего алгоритма =/= составить этот алгоритм.
                              Существование алгоритма не означает его практическую применимость. Поэтому заметка по ссылке кажется мне в лучшем случае фантазёрской (в худшем — бредовой).

                              Я понимаю, о чём вы говорите, но не вижу здесь ответа на свой вопрос.
                              • +1
                                Доказать существование некоего алгоритма =/= составить этот алгоритм.

                                Это правда, но для NP-полных задач существует оптимальный алгоритм (алгоритм Левина), который в случае P = NP будут работать полиномиальное время.

                                Существование алгоритма не означает его практическую применимость.

                                Это правда. Хотя я не знаю естественного примера задачи из P, у которой нет «применимого» алгоритма (бывают алгоритмы с большими константами, да, но на практике обычно оказывается, что есть алгоритм с немного большим полиномом и маленькими константами, который уже можно применять на практике).

                                Поэтому заметка по ссылке кажется мне в лучшем случае фантазёрской (в худшем — бредовой).

                                Вы видимо не учитываете, что это статья по математике, а не по программированию.

                                Попробую ещё раз ответить на ваш вопрос:
                                Что изменится, когда будет доказано равенство либо неравенство этих классов?

                                Это будет прорыв для теории, но на практике может ничего не измениться. Как ничего не изменило решение большой теоремы Ферма или подтверждение гипотезы Пуанкаре. В обоих случаях может оказаться, что никаких прикладных результатов из этого не последует.
                                • 0
                                  Спасибо, теперь намного понятнее, и ближе к моим интуитивным представлениям :)
                                  • –1
                                    Если будет доказано равенство то
                                    1. Будут созданы оптимальные архиваторы. т.е. никаким образом нельзя будет сжать файл сильнее чем полученныв образом.
                                    2.Будут созданы оптимальные компиляторы, т.е. без доп предположений нельзя оптимизировать код лучше.
                                    3.Будет реализован поиск оптимальной нейронной сети (хотя думаю нейронные сети вымрут, так как появятся существенно более эффективные алгоритмы)
                                    • 0
                                      1. «Оптимальный» компилятор — это как? Любой архиватор сжимает 99% входов не более, чем на 11 битов. Сжатие — это понятие немного другой области, из теории информации, а не из теории сложности вычислений.

                                      2. Что значит «нельзя оптимизировать код лучше»? И откуда это следует.
                                      Это вы фантазируете или имеются в виду какие-то конкретные результаты?

                                      3. Здесь я могу придумать определение оптимальности, но оно будет зависеть от распределения на входах. Действительно, для некоторых задач комбинаторной оптимизации P=NP позволяет получить полиномиальный алгоритм. Проблема только в том, что распределение входов для нейросети обычно неизвестно.
                                      • 0
                                        1. переформулирую
                                        пусть у нас есть некоторый алгоритм+память считаем размер общий.
                                        можно ли при ограничении по размеру памяти+алгоритма получить заданную последовательность за конечное число шагов.
                                        Если нет — увеличиваем память на 1 и повторяем.
                                        Сертификат задачи — данные.

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

                                        3. построение оптимального дерева разбора. грубо xgboost сразу с оптимальными параметрами.

                                        • 0
                                          1.
                                          По размеру памяти+алгоритма получить заданную последовательность за конечное число шагов.

                                          И как вы это будете проверять? Вы упираетесь в проблему останова, которая неразрешима.
                                          • 0
                                            Проблема останова не разрешима для бесконечной памяти. Для конечной памяти количество состояний конечно.
                                            • 0
                                              ОК. Думал, что память — это размер выхода. Всё равно не понимаю, почему это задача из NP. Что является входом? Что является сертификатом? Почему проверка сертификата занимает полиномиальное время?
                                              • 0
                                                Вход — сжатые данные (начальное состояние программы) — выход разжатый размер.
                                                Сертификат такое начальное состояние что приводит к разархивации файла.
                                                • 0
                                                  Вход — сжатые данные (начальное состояние программы) — выход разжатый размер.

                                                  Это архиватор? На выходе «разжатые данные» или их размер?
                                                  Куда делись «алгоритм+память»? Вы пишете, что «начальное состояние» это и «сжатые данные» и сертификат. Не понимаю, что имеется в виду. Можете описать задачу математически? Может быть тогда все вопросы отпадут.
                                                  • 0
                                                    Пусть есть алгоритм включающий А: распаковщик+сжатые данные(размера А). Расширим программу Б: ячейками заполненными нулями (размера Б) предполагаем что память циклична и кода не может включать исключения(ошибки вызывающие останов). С: Расжатые данные.
                                                    Т.е. Алгоритму нужно заполнить А такими значениями что бы в результате выполнения получался на выходе С.

                                                    Сертификат это отображение сжатых данных(А) на разжатые данные(С). проверяется исполнением программы.
                                                    • 0
                                                      Т.е. время проверки может быть 2^|Б|?
                                                      • 0
                                                        cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

                                                        (гугл перевод)
                                                        Поскольку все проблемы с NP- полной оптимизацией становятся легкими, все будет намного более эффективно. Транспортировка всех форм будет оптимально спланирована, чтобы быстрее и дешевле перемещать людей и товары. Производители могут улучшить свое производство, чтобы увеличить скорость и уменьшить количество отходов. И я просто царапаю поверхность.

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

                                                        P = NP также будет иметь большое значение в математике. Можно найти краткие, вполне логичные доказательства для теорем, но эти доказательства обычно чрезвычайно велики. Но мы можем использовать принцип бритвы Оккама для распознавания и проверки математических доказательств, как правило, написанных в журналах. Затем мы можем найти доказательства теорем, которые имеют обоснованные доказательства длины, менее чем на 100 страницах. Человек, который доказывает, что P = NP, будет ходить домой из Института Клея не с проверкой в ​​1 миллион долларов, а с семью (фактически шесть, поскольку гипотеза Пуанкаре оказывается решена).

                                                        Не возлагайте надежды. Теоретики сложности вообще считают P ≠ NP, и такой красивый мир не может существовать.
                                                        • 0
                                                          Вы не ответили на вопрос, как будет устроена проверка того, что программа со входом A и ограничением на память B завершается с выходом C? Насколько я понимаю, эта задача полна для PSPACE. Из P = NP не следует, что P = PSPACE.
                                                          • 0
                                                            откуда вы берете PSPACE? если всего состояний 2^|A|, а PSPACE требует 2^(|A|^p)
                                                            • 0
                                                              откуда вы берете PSPACE?

                                                              Возьмём задачу X из PSPACE и сведём её в задаче «проверить, что программа со входом А и памятью B завершается выходом С»: программа — программа для решения X, A — вход для X, B — ограничение на память для X, а выходы нужно перебрать (для этого нужно дополнительное место, но оно длины |C|). Таким образом мы за полиномиальную память сведём любую PSPACE задачу к этой.

                                                              если всего состояний 2^|A|, а PSPACE требует 2^(|A|^p)

                                                              Это утверждение я не понял. Что значит «требует»?
                                                              Мне кажется, что вы запутались в иерархии классов. Из того, что P=NP, не следует, что любой экспоненциальный алгоритм имеет полиномальный аналог. Из P=NP не следует P=E (или EXP). Более того, P!=E, это безусловный результат, «иерархия по времени». Из того, что P=NP, следует только коллапс полиномиальной иерархии. То есть полиномиальные алгоримты появятся у тех задач, которые можно записать с константным количеством кванторов «существует» и «для любого».
                                                              • 0
                                                                Хорошо, пусть вычислительное время разархивации ограничено А^10.
                                                                • 0
                                                                  Тогда мы возвращаемся к исходному вопросу: что значит, что архиватор «оптимальный»? =) Думаю, что я понял, что вы хотите сделать, но мне кажется, что не очень корректно говорить об «оптимальном архиваторе» в данных терминах, т.к. нам приходится одновременно накладывать ограничения и на память и на время.
                                                                  • 0
                                                                    Это придумал не я.
                                                                    Была теорема о том, что можно построить оптимальный архиватор (и оптимальный компилятор) и в ней не было ограничение на время исполнения.
                                                                    Но найти я ее не могу. Вчера часа 2 искал.
                                                                    для компилятора доказательство вообще не вникал, а вот для архиватора в общих чертах я тут описал, насколько хватило способностей.
                                                                    • 0
                                                                      Я верю, что можно так определить понятие «оптимальный архиватор», что в предположении P=NP, он будет существовать ;-)
                                                                      • 0
                                                                        У Бейсона(вроде так пишется) вообще был комментарий (не найду) что доказать P=NP или P!=NP не возможно так как математика возможно противоречива (ZFC). Он занимался этой проблемой много лет.
                                                                        • 0
                                                                          Да, у этого вопроса есть три возможных решения: P=NP, P!=NP и «недоказуемо». Если ZFC противоречива, то там одновременно могут быть доказательства и P=NP, и P!=NP. Вопрос скорей всего в том, что ZFC по теореме Гёделя неполна, т.е. есть недоказуемые в ней [верные] утверждения.
                                                                          • 0
                                                                            Ну есть еще возможность построения неконструктивного доказательства с невозможностью построения конструктивного.
                                                                            Там вариантов больше чем 3.
                                                                            • 0
                                                                              Вот это я не очень понимаю. Любое доказательство P=NP будет означать, что оптимальный алгоритм для NP-полных задач (алгоритм Левина) является полиномиальным. Т.е. даже «неконструктивное» доказательство P=NP, позволяет получить явный полиномиальный алгоритм для NP-полных задач. Никто не будет, конечно, применять алгоритм Левина на практике, но всё же это совершенно конкретный алгоритм.
                                                                              • 0
                                                                                «неконструктивное» доказательство P=NP, НЕ позволяет получить явный полиномиальный алгоритм

                                                                                потому что оно неконструктивное.
                                                                                • 0
                                                                                  Алгоритм Левина оптимальный, следовательно, если P=NP, то он полиномиальный. В каком месте этого утверждения ошибка?
                                                                                  • 0
                                                                                    Доказательство существование <> построению алгоритма.
                                                                                    • 0

                                                                                      Так ведь такой алгоритм уже построен! Для алгоритма Левина верна следующая теорема.
                                                                                      Теорема:
                                                                                      Если P=NP, то существует такой полином p, что алгоритм Левина решает SAT за время p(n).

                                                                                      • 0

                                                                                        Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission, 9:265–266, 1973.

                                          • +1
                                            Сжатие — это понятие немного другой области, из теории информации, а не из теории сложности вычислений.
                                            Можно связать колмогоровскую сложность с самораспаковывающимися архивами. Хотя не представляю, как такой подход использовать в реальном софте.
                                            • 0
                                              Не очень понятно, почему архивы обязательно должны быть самораспаковывающиеся. В терминах Колмоговорской сложности это не очень важно, т.к. можно рассматривать сложность относительно деархиватора и она будет не более, чем на константу меньше, чем относительно универсальной машины (эта константа <= длина кода деархиватора).

                                              Как использовать Колмогоровскую сложность в софте я не знаю, но она, например, хорошо объясняет, какие строки нельзя сжать.
                                              • 0
                                                Там по ссылке наверное действительно не очень понятно, почему они взяли самораспаковывающийся архив. Мне кажется, это просто по определению колмогоровской сложности. В длине кода деархиватора как раз и «зашифрована» связь с теорией сложности вычислений, но так как изначально пост был про время вычислений, а не занимаемое место, то, наверное, колмогоровская сложность не совсем по теме.
                                                • 0
                                                  Тут просто. за полиномиальное время мы можем получить ответ можно ли создать размера N самораспаковывающийся архив содержащий упаковываемую информацию.
                                                  мы можем просто перебрать все значения это экспонента или если есть алгоритм np=p то создать такой файл за полиномиальное время.
                                                  аналогично с компиляцией.
                                                  • 0
                                                    С обычным архивом это вышло бы, но в самораспаковывающимся есть одна хитрость, которая, по-моему, хорошо иллюстрирует, почему колмогоровская сложность не вычислима. Там же можно формально перебирать и кусок кода-деархиватора, то есть создание оптимального самораспаковывающегося архива будет эквивалентно решению проблемы остановки машины Тьюринга, которая алгоритмически неразрешима.
                                                    • 0
                                                      Задача решается на ограниченной памяти.
                                                      Заметьте, что NP=P позволит доказать ВСЕ теоремы доказательства размер которых не будет превышать указанный размер. (естественно понимается что степень будет небольшая и константа тоже не особо большой).
                                                      • 0
                                                        Там выше, вроде, это уже обсуждалось.
                                                        • 0
                                                          Да. я приводил ссылку.
                                                          • 0
                                                            Ссылка на P vs NP, но с таким архивом получается дальнейшее усложнение: P vs NP vs PSPACE… Что-то не готов лезть в такие дебри.
                                                    • +1
                                                      за полиномиальное время мы можем получить ответ можно ли создать размера N самораспаковывающийся архив содержащий упаковываемую информацию
                                                      Верно ли, что проверка — это запуск алгоритма? Но что если алгоритм длины N, генерирующий заданную последовательность, существует, но время его работы — exp(N)? Тогда проверка не за полиномиальное время.
                                              • +1
                                                Это вы фантазируете или имеются в виду какие-то конкретные результаты?

                                                Автор, конечно, вряд ли имел это в виду, но в компиляторах полно NP-полных задач: аллокация регистров, instruction scheduling, минимизация количества барьеров памяти.


                                                Речи о "нельзя оптимизировать код лучше", конечно, не идет, но практический (да пусть даже и экспоненциальный) алгоритм может дать мощный толчок компиляторным оптимизациям.

                                        • 0
                                          неизвестно, существует ли криптографически стойкие шифры

                                          А как же Шифр Вернама?
                                          • 0
                                            А как же Шифр Вернама?

                                            Шифр Вернама является стойким безусловно, но у него длина ключа должна быть не менее длины сообщения (правильнее говорить не про длины, а про энтропию).
                                            Тут же я имел в виду шифры, у которых длина ключа не зависит от длины пересылаемого текста.
                                        • +3
                                          Самое важное — это большая теоретическая задача. Есть тысячи условных утверждений вида «Если P != NP, то...». С ее решением брюки превращаются они становятся безусловными.

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                        Самое читаемое