Comments 76
UFO just landed and posted this here
Интуиция? Или есть более строгое докозательство сего утверждения? Интересно…
Если бы это было алгоритмически доказуемо, то наверное было бы P==NP. Опять-таки интуиция. Но тут вполне возможно что-то связанное с парадоксами и неполнотой формальных систем.
Интуитивно наоборот же, P != NP. Вы же не сможете решить, например, шахматы, не перебирая экспоненциальное число позиций в зависимости от глубины
Шахматы — это плохой пример, т.к. это конечная игра, которая описывается деревом глубины 50, т.е. поиск оптимальной стратегии не просто лежит в P, а решается за константу.
Думаю, что под словами «алгоритмически доказуемо» выше понимается «доказательство предъявлением алгоритма». И тогда понятно, что таким образом значительно «проще» доказать P = NP (например, предъявить полиномиальный алгоритм для NP-полной задачи), чем доказать, что такого алгоритма не существует (непонятно, какой алгоритм для этого нужно предъявить).
Думаю, что под словами «алгоритмически доказуемо» выше понимается «доказательство предъявлением алгоритма». И тогда понятно, что таким образом значительно «проще» доказать P = NP (например, предъявить полиномиальный алгоритм для NP-полной задачи), чем доказать, что такого алгоритма не существует (непонятно, какой алгоритм для этого нужно предъявить).
Т.е. построить конструктивное доказательство P != NP не возможно?
Я этого не утверждал, а лишь попытался угадать мотивацию из комментария выше. Сейчас очень популярны результаты, которые связывают верхние оценки (эффективные алгоритмы) и нижние оценки (отсутствие эффективных алгоритмов). Наиболее известен результат Раена Вильямса о том, что класс NEXP не лежит в классе ACC. Вильямс доказывает, что для некоторой сложной задачи есть алгоритм более эффективный, чем перебор, и из этого следует, что NEXP не лежит в ACC. То есть такое доказательство теоретически возможно.
Почему же? Насколько я понял, доказательство в статье как раз конструктивное: приводится контрпример, задача из NP, для которой нет полиномиального алгоритма.
Хорошо, вот вам масштабируемая задача: определить точное значение коми (преимущество делающего первый ход игрока) для игры Го на доске размера NxN, как функция от параметра N.
Посмотрите комментарий, на который я отвечал. Там шахматы приводились как пример, где интуитивно понятно, что потребуется экспоненциальный перебор. На что я заметил, что это плохой пример и объяснил почему.
Ваш пример, ИМХО, тоже плохой. Во-первых, задача менее понятная, т.к. требует знание правил Го и соответственной интуиции в Го. Во-вторых, мне вот совсем не _интуитивно понятно_, что задача, которую Вы преложили — это задача, которая может быть решена только экспоненциальным перебором (даже если это действительно так, хотя без исследования этого вопроса у меня есть большие сомнения).
Ваш пример, ИМХО, тоже плохой. Во-первых, задача менее понятная, т.к. требует знание правил Го и соответственной интуиции в Го. Во-вторых, мне вот совсем не _интуитивно понятно_, что задача, которую Вы преложили — это задача, которая может быть решена только экспоненциальным перебором (даже если это действительно так, хотя без исследования этого вопроса у меня есть большие сомнения).
И как решение этой задачи планируется проверять за полиноминальное время? Мне вот почему-то кажется, что эта задача в класс NP не попадает.
Я и не спорю. Но в предыдущем комментарии я предположил несколько другое.
Например, известный эксперт по сложности и квантовым вычисленим Скотт Ааронсон поставил $200 тыс. на то, что доказательство не верно.Не совсем, он пишет «я поставил бы, как в прошлый раз...». Он уже один раз отредактировал свой блог, убрав ссылку на неверное сообщение об ошибке, Любош Мотль по этому поводу ещё позлобствовал.
Вы правы, спасибо, пропустил «бы»! Поправил в статье. Комментарий Мотля забавный =)
Если вдруг не видели, реакция Ааронсона с «Мюбошем Лотлем».
Предыдущие 116 «доказательств»: www.win.tue.nl/~gwoegi/P-versus-NP.htm
Эта ссылка есть в посте, спасибо. В посте также объясняется, чем это доказательство отличается от других.
Извиняюсь, ссылку пропустил…
Но на счет «чем-то» отличается, у меня достаточно много скептицизма тут.
Аппеляция к личности автора, к сожалению, вряд ли можно считать за существенное отличие. Ну а в плане техники… все-таки, глобально, это всего лишь «еще одно доказательство в списке». Потому что у всех 116 тоже есть что-то отличное в технике.
Думаю, поднимать хайп пока еще очень и очень рано.
Но на счет «чем-то» отличается, у меня достаточно много скептицизма тут.
Аппеляция к личности автора, к сожалению, вряд ли можно считать за существенное отличие. Ну а в плане техники… все-таки, глобально, это всего лишь «еще одно доказательство в списке». Потому что у всех 116 тоже есть что-то отличное в технике.
Думаю, поднимать хайп пока еще очень и очень рано.
Но на счет «чем-то» отличается, у меня достаточно много скептицизма тут.
И не у вас одного. Однако более 50-ти доказательств, появившиеся после доказательства Деолаликара 2010 года, прошли незамеченными. В то время как доказательство Блюма привлекло пристальное внимание комьюнити и о нём уже написала значительная часть блоггеров-экспертов по теории сложности.
Думаю, поднимать хайп пока еще очень и очень рано.
Не спорю. Как я уже написал, скорей всего ошибку найдут довольно быстро. Тем более, что появился комментарий от Разборова, который вроде как объясняет, почему в доказательстве должна быть ошибка (хотя саму ошибку пока никто не нашёл).
Я наверное ошибаюсь, но разве уже не доказали, что это в принципе недоказуемо?
Как указано в 1-ом ответе на stackexchange, Alexander Razborov полагает что это доказательство Блюма не верно, и что в 6 теореме доказательства есть ошибка
Update: Пока я писал этот пост,
Пока один пишет статью на хабр, а другой этот бессмысленный коммент к статье, кто-то успевает решать и опровергать решение задач тысячелетия. Дорогая редакция, пристрели мне карму, может тогда тоже сделаю что-то полезное.
Чо тут доказывать
P=np только когда n=1
Во всех остальных случаях не равно
Як диты
P=np только когда n=1
Во всех остальных случаях не равно
Як диты
Разборов у нас вёл просеминар по математической логике для студентов первого курса в 1987 году. Он сам тогда только закончил МГУ. Разборов, Шень и Верещагин, втроём.
Почему это важная задача? Что изменится, когда будет доказано равенство либо неравенство этих классов? Особенно неравенство. Интуитивно кажется, что они не могут быть равны, но могу также поверить, что они могут быть эквивалентны, но у алгоритмов решения полной задачи за линейное время такая вычислительная сложность каждого шага, что практически такой алгоритм ни для чего не годится.
Большинство прикладных задач лежат в классе NP, но далеко не для всех из них существуют эффективные алгоритмы. Вопрос о равенстве классов P и NP, это вопрос о том, есть ли надежда научиться решать эти задачи эффективно или нет. Без разрешения этого вопроса, например, неизвестно, существует ли криптографически стойкие шифры (если P=NP, то односторонних функций нет, а следовательно нет и стойких шифров).
Как будет устроен мир при различных исходах хорошо описано в статье Рассела Импальяццо, перевод которой есть на хабре: habrahabr.ru/post/132127
Как будет устроен мир при различных исходах хорошо описано в статье Рассела Импальяццо, перевод которой есть на хабре: habrahabr.ru/post/132127
Доказать существование некоего алгоритма =/= составить этот алгоритм.
Существование алгоритма не означает его практическую применимость. Поэтому заметка по ссылке кажется мне в лучшем случае фантазёрской (в худшем — бредовой).
Я понимаю, о чём вы говорите, но не вижу здесь ответа на свой вопрос.
Существование алгоритма не означает его практическую применимость. Поэтому заметка по ссылке кажется мне в лучшем случае фантазёрской (в худшем — бредовой).
Я понимаю, о чём вы говорите, но не вижу здесь ответа на свой вопрос.
Доказать существование некоего алгоритма =/= составить этот алгоритм.
Это правда, но для NP-полных задач существует оптимальный алгоритм (алгоритм Левина), который в случае P = NP будут работать полиномиальное время.
Существование алгоритма не означает его практическую применимость.
Это правда. Хотя я не знаю естественного примера задачи из P, у которой нет «применимого» алгоритма (бывают алгоритмы с большими константами, да, но на практике обычно оказывается, что есть алгоритм с немного большим полиномом и маленькими константами, который уже можно применять на практике).
Поэтому заметка по ссылке кажется мне в лучшем случае фантазёрской (в худшем — бредовой).
Вы видимо не учитываете, что это статья по математике, а не по программированию.
Попробую ещё раз ответить на ваш вопрос:
Что изменится, когда будет доказано равенство либо неравенство этих классов?
Это будет прорыв для теории, но на практике может ничего не измениться. Как ничего не изменило решение большой теоремы Ферма или подтверждение гипотезы Пуанкаре. В обоих случаях может оказаться, что никаких прикладных результатов из этого не последует.
Спасибо, теперь намного понятнее, и ближе к моим интуитивным представлениям :)
Если будет доказано равенство то
1. Будут созданы оптимальные архиваторы. т.е. никаким образом нельзя будет сжать файл сильнее чем полученныв образом.
2.Будут созданы оптимальные компиляторы, т.е. без доп предположений нельзя оптимизировать код лучше.
3.Будет реализован поиск оптимальной нейронной сети (хотя думаю нейронные сети вымрут, так как появятся существенно более эффективные алгоритмы)
1. Будут созданы оптимальные архиваторы. т.е. никаким образом нельзя будет сжать файл сильнее чем полученныв образом.
2.Будут созданы оптимальные компиляторы, т.е. без доп предположений нельзя оптимизировать код лучше.
3.Будет реализован поиск оптимальной нейронной сети (хотя думаю нейронные сети вымрут, так как появятся существенно более эффективные алгоритмы)
1. «Оптимальный» компилятор — это как? Любой архиватор сжимает 99% входов не более, чем на 11 битов. Сжатие — это понятие немного другой области, из теории информации, а не из теории сложности вычислений.
2. Что значит «нельзя оптимизировать код лучше»? И откуда это следует.
Это вы фантазируете или имеются в виду какие-то конкретные результаты?
3. Здесь я могу придумать определение оптимальности, но оно будет зависеть от распределения на входах. Действительно, для некоторых задач комбинаторной оптимизации P=NP позволяет получить полиномиальный алгоритм. Проблема только в том, что распределение входов для нейросети обычно неизвестно.
2. Что значит «нельзя оптимизировать код лучше»? И откуда это следует.
Это вы фантазируете или имеются в виду какие-то конкретные результаты?
3. Здесь я могу придумать определение оптимальности, но оно будет зависеть от распределения на входах. Действительно, для некоторых задач комбинаторной оптимизации P=NP позволяет получить полиномиальный алгоритм. Проблема только в том, что распределение входов для нейросети обычно неизвестно.
1. переформулирую
пусть у нас есть некоторый алгоритм+память считаем размер общий.
можно ли при ограничении по размеру памяти+алгоритма получить заданную последовательность за конечное число шагов.
Если нет — увеличиваем память на 1 и повторяем.
Сертификат задачи — данные.
2. полностью аналогично для задачи компиляции. Есть входная и выходная последовательности надо их сделать эквивалентными по результату. Тут есть нюанс, данный алгоритм должен быть всегда конечным, даже больше — ограничен заранее заданным размером по памяти и числу шагов выполнения.
3. построение оптимального дерева разбора. грубо xgboost сразу с оптимальными параметрами.
пусть у нас есть некоторый алгоритм+память считаем размер общий.
можно ли при ограничении по размеру памяти+алгоритма получить заданную последовательность за конечное число шагов.
Если нет — увеличиваем память на 1 и повторяем.
Сертификат задачи — данные.
2. полностью аналогично для задачи компиляции. Есть входная и выходная последовательности надо их сделать эквивалентными по результату. Тут есть нюанс, данный алгоритм должен быть всегда конечным, даже больше — ограничен заранее заданным размером по памяти и числу шагов выполнения.
3. построение оптимального дерева разбора. грубо xgboost сразу с оптимальными параметрами.
1.
И как вы это будете проверять? Вы упираетесь в проблему останова, которая неразрешима.
По размеру памяти+алгоритма получить заданную последовательность за конечное число шагов.
И как вы это будете проверять? Вы упираетесь в проблему останова, которая неразрешима.
Проблема останова не разрешима для бесконечной памяти. Для конечной памяти количество состояний конечно.
ОК. Думал, что память — это размер выхода. Всё равно не понимаю, почему это задача из NP. Что является входом? Что является сертификатом? Почему проверка сертификата занимает полиномиальное время?
Вход — сжатые данные (начальное состояние программы) — выход разжатый размер.
Сертификат такое начальное состояние что приводит к разархивации файла.
Сертификат такое начальное состояние что приводит к разархивации файла.
Вход — сжатые данные (начальное состояние программы) — выход разжатый размер.
Это архиватор? На выходе «разжатые данные» или их размер?
Куда делись «алгоритм+память»? Вы пишете, что «начальное состояние» это и «сжатые данные» и сертификат. Не понимаю, что имеется в виду. Можете описать задачу математически? Может быть тогда все вопросы отпадут.
Пусть есть алгоритм включающий А: распаковщик+сжатые данные(размера А). Расширим программу Б: ячейками заполненными нулями (размера Б) предполагаем что память циклична и кода не может включать исключения(ошибки вызывающие останов). С: Расжатые данные.
Т.е. Алгоритму нужно заполнить А такими значениями что бы в результате выполнения получался на выходе С.
Сертификат это отображение сжатых данных(А) на разжатые данные(С). проверяется исполнением программы.
Т.е. Алгоритму нужно заполнить А такими значениями что бы в результате выполнения получался на выходе С.
Сертификат это отображение сжатых данных(А) на разжатые данные(С). проверяется исполнением программы.
Т.е. время проверки может быть 2^|Б|?
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, и такой красивый мир не может существовать.
(гугл перевод)
Поскольку все проблемы с NP- полной оптимизацией становятся легкими, все будет намного более эффективно. Транспортировка всех форм будет оптимально спланирована, чтобы быстрее и дешевле перемещать людей и товары. Производители могут улучшить свое производство, чтобы увеличить скорость и уменьшить количество отходов. И я просто царапаю поверхность.
Обучение упрощается, используя принцип бритвы Оккама — мы просто находим самую маленькую программу, соответствующую данным. Почти идеальное распознавание зрения, понимание языка и перевод и все другие учебные задачи становятся тривиальными. Мы также будем иметь гораздо лучшие прогнозы погоды и землетрясений и других природных явлений.
P = NP также будет иметь большое значение в математике. Можно найти краткие, вполне логичные доказательства для теорем, но эти доказательства обычно чрезвычайно велики. Но мы можем использовать принцип бритвы Оккама для распознавания и проверки математических доказательств, как правило, написанных в журналах. Затем мы можем найти доказательства теорем, которые имеют обоснованные доказательства длины, менее чем на 100 страницах. Человек, который доказывает, что P = NP, будет ходить домой из Института Клея не с проверкой в 1 миллион долларов, а с семью (фактически шесть, поскольку гипотеза Пуанкаре оказывается решена).
Не возлагайте надежды. Теоретики сложности вообще считают P ≠ NP, и такой красивый мир не может существовать.
Вы не ответили на вопрос, как будет устроена проверка того, что программа со входом A и ограничением на память B завершается с выходом C? Насколько я понимаю, эта задача полна для PSPACE. Из P = NP не следует, что P = PSPACE.
откуда вы берете PSPACE? если всего состояний 2^|A|, а PSPACE требует 2^(|A|^p)
откуда вы берете 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, следует только коллапс полиномиальной иерархии. То есть полиномиальные алгоримты появятся у тех задач, которые можно записать с константным количеством кванторов «существует» и «для любого».
Хорошо, пусть вычислительное время разархивации ограничено А^10.
Тогда мы возвращаемся к исходному вопросу: что значит, что архиватор «оптимальный»? =) Думаю, что я понял, что вы хотите сделать, но мне кажется, что не очень корректно говорить об «оптимальном архиваторе» в данных терминах, т.к. нам приходится одновременно накладывать ограничения и на память и на время.
Это придумал не я.
Была теорема о том, что можно построить оптимальный архиватор (и оптимальный компилятор) и в ней не было ограничение на время исполнения.
Но найти я ее не могу. Вчера часа 2 искал.
для компилятора доказательство вообще не вникал, а вот для архиватора в общих чертах я тут описал, насколько хватило способностей.
Была теорема о том, что можно построить оптимальный архиватор (и оптимальный компилятор) и в ней не было ограничение на время исполнения.
Но найти я ее не могу. Вчера часа 2 искал.
для компилятора доказательство вообще не вникал, а вот для архиватора в общих чертах я тут описал, насколько хватило способностей.
Я верю, что можно так определить понятие «оптимальный архиватор», что в предположении P=NP, он будет существовать ;-)
У Бейсона(вроде так пишется) вообще был комментарий (не найду) что доказать P=NP или P!=NP не возможно так как математика возможно противоречива (ZFC). Он занимался этой проблемой много лет.
Да, у этого вопроса есть три возможных решения: P=NP, P!=NP и «недоказуемо». Если ZFC противоречива, то там одновременно могут быть доказательства и P=NP, и P!=NP. Вопрос скорей всего в том, что ZFC по теореме Гёделя неполна, т.е. есть недоказуемые в ней [верные] утверждения.
Ну есть еще возможность построения неконструктивного доказательства с невозможностью построения конструктивного.
Там вариантов больше чем 3.
Там вариантов больше чем 3.
Вот это я не очень понимаю. Любое доказательство P=NP будет означать, что оптимальный алгоритм для NP-полных задач (алгоритм Левина) является полиномиальным. Т.е. даже «неконструктивное» доказательство P=NP, позволяет получить явный полиномиальный алгоритм для NP-полных задач. Никто не будет, конечно, применять алгоритм Левина на практике, но всё же это совершенно конкретный алгоритм.
Сжатие — это понятие немного другой области, из теории информации, а не из теории сложности вычислений.Можно связать колмогоровскую сложность с самораспаковывающимися архивами. Хотя не представляю, как такой подход использовать в реальном софте.
Не очень понятно, почему архивы обязательно должны быть самораспаковывающиеся. В терминах Колмоговорской сложности это не очень важно, т.к. можно рассматривать сложность относительно деархиватора и она будет не более, чем на константу меньше, чем относительно универсальной машины (эта константа <= длина кода деархиватора).
Как использовать Колмогоровскую сложность в софте я не знаю, но она, например, хорошо объясняет, какие строки нельзя сжать.
Как использовать Колмогоровскую сложность в софте я не знаю, но она, например, хорошо объясняет, какие строки нельзя сжать.
Там по ссылке наверное действительно не очень понятно, почему они взяли самораспаковывающийся архив. Мне кажется, это просто по определению колмогоровской сложности. В длине кода деархиватора как раз и «зашифрована» связь с теорией сложности вычислений, но так как изначально пост был про время вычислений, а не занимаемое место, то, наверное, колмогоровская сложность не совсем по теме.
Тут просто. за полиномиальное время мы можем получить ответ можно ли создать размера N самораспаковывающийся архив содержащий упаковываемую информацию.
мы можем просто перебрать все значения это экспонента или если есть алгоритм np=p то создать такой файл за полиномиальное время.
аналогично с компиляцией.
мы можем просто перебрать все значения это экспонента или если есть алгоритм np=p то создать такой файл за полиномиальное время.
аналогично с компиляцией.
С обычным архивом это вышло бы, но в самораспаковывающимся есть одна хитрость, которая, по-моему, хорошо иллюстрирует, почему колмогоровская сложность не вычислима. Там же можно формально перебирать и кусок кода-деархиватора, то есть создание оптимального самораспаковывающегося архива будет эквивалентно решению проблемы остановки машины Тьюринга, которая алгоритмически неразрешима.
Задача решается на ограниченной памяти.
Заметьте, что NP=P позволит доказать ВСЕ теоремы доказательства размер которых не будет превышать указанный размер. (естественно понимается что степень будет небольшая и константа тоже не особо большой).
Заметьте, что NP=P позволит доказать ВСЕ теоремы доказательства размер которых не будет превышать указанный размер. (естественно понимается что степень будет небольшая и константа тоже не особо большой).
Там выше, вроде, это уже обсуждалось.
Да. я приводил ссылку.
Ссылка на P vs NP, но с таким архивом получается дальнейшее усложнение: P vs NP vs PSPACE… Что-то не готов лезть в такие дебри.
за полиномиальное время мы можем получить ответ можно ли создать размера N самораспаковывающийся архив содержащий упаковываемую информациюВерно ли, что проверка — это запуск алгоритма? Но что если алгоритм длины N, генерирующий заданную последовательность, существует, но время его работы — exp(N)? Тогда проверка не за полиномиальное время.
Это вы фантазируете или имеются в виду какие-то конкретные результаты?
Автор, конечно, вряд ли имел это в виду, но в компиляторах полно NP-полных задач: аллокация регистров, instruction scheduling, минимизация количества барьеров памяти.
Речи о "нельзя оптимизировать код лучше", конечно, не идет, но практический (да пусть даже и экспоненциальный) алгоритм может дать мощный толчок компиляторным оптимизациям.
неизвестно, существует ли криптографически стойкие шифры
А как же Шифр Вернама?
Самое важное — это большая теоретическая задача. Есть тысячи условных утверждений вида «Если P != NP, то...». С ее решением брюки превращаются они становятся безусловными.
Sign up to leave a comment.
Новая заявка на решение задачи P vs. NP