Опубликовано доказательство P!=NP

[Xaositect]

Dandan в сообщении #343812 писал(а):

Можно еще так сказать. Вот есть у вас какой-то алгоритм. Вы можете просчитать некоторые значения и составить другой алгоритм с таблицей, в которой сохранены подсчитанные значения. Он будет больше по "размеру", но будет работать в общем быстрее (все-таки O(1) на закешированных значения, если не учитывать считывание входа и запись выхода). Конечно, в пределе эти алгоритмы будут одинаковы, но факт более быстрого подсчета некоторых значений остается.

Это верно, но к проблеме P-NP имеет мало отношения - там рассматривается именно асимптотическое поведение на длинных входных значениях.

-- Ср авг 11, 2010 17:02:10 --

Кстати, для машин Тьюринга мы можем вообще любую программу ускорить в константное число раз при $n\to\infty$ (linear speedup theorem), так что о конечном количестве входов можно вообще не париться.
Можно посчитать, насколько при этом программа вырастет.

[sergey83]

Скажите, а dxdy.ru - это единственный русскоязычный форум, где обсуждаются научные проблемы? Или в рунете есть другие математические форумы, где можно было бы почитать обсуждение доказательства P!=NP ?

[maxal]

sergey83 в сообщении #343900 писал(а):

Или в рунете есть другие математические форумы, где можно было бы почитать обсуждение доказательства P!=NP ?

Я видел только пару обсуждений в ЖЖ:
http://yvl.livejournal.com/14141.html
http://avva.livejournal.com/2250953.html

[Dandan]

Xaositect в сообщении #343814 писал(а):

Это верно, но к проблеме P-NP имеет мало отношения - там рассматривается именно асимптотическое поведение на длинных входных значениях.

Кстати, для машин Тьюринга мы можем вообще любую программу ускорить в константное число раз при $n\to\infty$ (linear speedup theorem), так что о конечном количестве входов можно вообще не париться.
Можно посчитать, насколько при этом программа вырастет.

Может к самой проблеме и не имеет отношения, но имеет отношение к следствиям из нее.
Вот допустим мы хотим решить задачу факторизации для чисел размером не более 2к бит. Теоретически существует алгоритм, который это быстро делает, но занимает при этом порядка $2^{2000}$ бит памяти (практически не досягаемое число). Так может тогда и существует алгоритм, который работает также быстро, но при этом занимает меньше памяти? Следует ли из P!=NP, что такого алгоритма не существует?

[Pavlovsky]

Dandan в сообщении #343929 писал(а):

Вот допустим мы хотим решить задачу факторизации для чисел размером не более 2к бит. Теоретически существует алгоритм, который это быстро делает, но занимает при этом порядка $2^{2000}$ бит памяти (практически не досягаемое число). Так может тогда и существует алгоритм, который работает также быстро, но при этом занимает меньше памяти? Следует ли из P!=NP, что такого алгоритма не существует?

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

[Xaositect]

Dandan в сообщении #343929 писал(а):

Следует ли из P!=NP, что такого алгоритма не существует?

Нет, не следует. P!=NP не имеет никакого отношения к алгоритмам с конечной областью входных данных.

-- Чт авг 12, 2010 11:49:20 --

Это ближе к колмогоровской сложности, погуглите resource-bounded kolmogorov complexity.

[Dandan]

Pavlovsky в сообщении #343940 писал(а):

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

Под памятью я имею ввиду не только ленту с ячейками, но и множество правил перехода. Информацию в $2^{2000}$ бит можно закодировать в этих правилах перехода, а ленту вообще оставить пустой и "подавать" на ленту только число для факторизации.

И че это за мода пошла посылать "к учебникам"? Товарищи, проще быть надо, проще...

-- Чт авг 12, 2010 19:10:41 --

Xaositect в сообщении #343965 писал(а):

Нет, не следует. P!=NP не имеет никакого отношения к алгоритмам с конечной областью входных данных.

-- Чт авг 12, 2010 11:49:20 --

Это ближе к колмогоровской сложности, погуглите resource-bounded kolmogorov complexity.

Если из этой теории сложности можно получить какие-то оценки на сложность алгоритмов с конечной областью входных данных, то из этих оценок, возможно, можно было бы сделать какой-то вывод для вопроса P?=NP. Это собсно идея, которую я и хотел выразить в самом начале. К тому же, этот вопрос (о сложности алгоритмов с конечной областью входных данных), по-моему, более важен для практической криптографии, чем P?=NP.

[sergey83]

Можно взять и все данные запихнуть в одну переменную. Пусть даже эта переменная X будет занимать $2^{2000}$ бит. Слышали, как криптографы ругаются, когда им приходится работать с длинными целыми? Так вот, теоретически можно создать машину, где простейшие операции с такими длинными целыми будут производится за один такт. И при оценке сложности алгоритма считать, что операции с X совершаются за один такт.
Как я понял, Dandan хотел не составлять большую хеш таблицу, а хотел расширить регистры.
Между тем, мы ускорим только простейшие операции с длинными целыми. Я думаю, что это не поможет изменить асимптотическую сложность алгоритма.

[sergey83]

Dandan в сообщении #343741 писал(а):

Ведь если у нас в компьютере бесконечная память, то теоретически могут существовать полностью всё покрывающие радужные таблицы. И тогда вообще все NP задачи могут быть решены за O(1).

Такая задача. Сколько нужно времени, чтобы вычислить значение полинома степени n от одной переменной x?
По схеме Горнера за n сложений и n умножений. А если разрешить предварительную обработку коэффициентов? Тогда за n/2 умножений и n сложений. Причем быстрее вообще нельзя.
Теперь введем ограничение. Пусть каждый коэффициент полинома занимает 4 байта. А переменная x может быть хоть double, хоть более длинной, короче, нет ограничения на x.
Допустим, память у нас бесконечная, доступ к ячейки памяти осуществляется за один такт. В математической модели машины с неограниченными регистрами также доступ к ячейки памяти осуществляется за один такт.
Если использовать радужные или любые другие хеш таблицы, то можно ли вычислять значение многочлена быстрее линейного времени?
Думаю, что нет. Например, для вычисления индекса хеш таблицы понадобится линейное время.

[Rasool]

В новостях на mail.ru прочитал:

Цитата:

Винэй Деолаликар, по мнению его коллег, представил некорректное доказательство двух классов задач.

Деолаликар, сотрудник Исследовательской лаборатории Hewlett-Packard в Пало-Альто, доказал неравенство задач классов P и NP. К классу P относятся те вычислительные задачи, которые (условно) легко решаются, а в группу NP входят задачи, решение которых легко проверить. Неравенство классов P и NP лежит в основе популярных криптографических алгоритмов.

Его метод вызвал критику коллег: профессиональных математиков Ричарда Липтона из Технологического института Джорджии и Скотта Ааронсона из Массачусетского технологического института. Результаты поиска ошибок они представили в своих блогах, сообщает Компьюлента.

В частности, Липтон приводит замечания своих коллег Нила Иммермана и Теренса Тао.

Иммерман обращает внимание на то, что Винэй Деолаликар, пытаясь показать, что некоторые проблемы входят в класс NP, но не попадают в Р, нарушает правила «обращения» с набором FO(LFP). Комментарий Теренса Тао касается задачи выполнимости булевых формул, при использовании которой в доказательстве, по мнению ученого, также были допущены ошибки.

В блоге Скотта Аронсона говорится, что Деолаликар не объясняет, почему доказательство не работает в случае некоторых вариаций NP-полных проблем (скажем, задачи выполнимости булевых формул в 2-конъюнктивной нормальной форме), входящих в класс Р.

Винэй Деолаликар надеется исправить этот и другие недочёты. В настоящее время он готовит «полный вариант» публикации – 121 страницу математических выкладок.

http://news.mail.ru/society/4295126/

[Zealint]

Как и ожидалось, начались успешные поиски "косяков". Например, здесь: http://lenta.ru/articles/2010/08/18/fail/

Посмотрим, что будет дальше...

[maxal]

А вот напротив "доказательство" P=NP - и кому теперь верить?

Цитата:

14 мая 2010 года была опубликована статья Пятлина Леонида Алексеевича «Полиномиальное решение труднорешаемых задач: P=NP» в рецензируемом научном Электронном математическом и медико-биологическом журнале «Математическая морфология» Т. 9, Вып. 2, 2010 г. под рубрикой Записки Смоленского Регионального отделения Научного Совета Российской Академии Наук «Методология искусственного интеллекта». http://www.smolensk.ru/user/sgma/MMORPH ... iatlin.htm

Копию статьи можно скачать с сайта изобретения http://www.polinomill.lact.ru/. Эта копия отличается от оригинала только устранением опечаток, возникших при публикации по техническим причинам и опечаток автора, не влияющих на смысл текста. http://www.polinomill.lact.ru.edit.lact ... _P_NP..doc

В статье автор приводит способ решения задачи Гамильтона с полиномиальными затратами седьмой степени путем определения всех негамильтоновых звеньев маршрутов и их удаления из описания всех маршрутов графа. Автор обосновывает в трех теоремах истинность алгоритма и его полиномиальности.

P.S. Это к вопросу о качестве рецензирования...

[creative]

maxal

Не поймите меня неправильно, я не предубеждён, но дизайн сайта polinomill.lact.ru настолько идиотский, что я бы не стал верить тому, что написано там, особенно если там идёт доказательство проблемы тысячелетия.

[Maslov]

(Оффтоп)

creative в сообщении #352871 писал(а):

Не поймите меня неправильно, я не предубеждён, но дизайн сайта polinomill.lact.ru настолько идиотский, что я бы не стал верить тому, что написано там

Объясните, пожалуйста, какое отношение имеет математическая квалификация к способности/желанию заниматься web-дезайном?
На мой взгляд, не большее, чем талант Ландау в физике к его же плохому почерку.

[venco]

Maslov, попробуйте почитать эту статью: http://www.smolensk.ru/user/sgma/MMORPH ... iatlin.htm
Я застрял на определении графа и "матрицы маршрута".