P ? NP Обсуждение, методы, мысли (Проблема перебора)

[SuperIntegral!]

Приветствую, Форумчане!

Заголовок темы кричит сам за себя. Вы, форумчане, уже, наверно, догадались, что в этой теме будет идти речь о одной из самых сложных и великих трудностей в математике/информатике!

Итак, проблема равенства классов $P = NP$. Рассмотрим пресловутую цитату из википедии wiki:

Цитата:

Вопрос о равенстве классов сложности P и NP - одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.

Предлагаю здесь начать обсуждение этой проблемы. Уверен многие пытались решать или думали о проблеме.
Как вы считаете, какой будет дан ответ на поставленный вопрос - они равны или нет?

От себя, новичка, добавлю пару детских вопросов - Знаменитая задача коммивояжёра, вроде бы не считается NP полной, но при ограничениях "существует ли маршрут не длиннее, чем некое заданное $n$" она полной считается? Например, в книге Иэн Стюарта имеется такая фраза -

Цитата:

Задача о коммивояжере является «почти» NP-полной,но здесь есть одна техническая сложность: мы не знаем, относится ли она к классу NP.

Ну и традиционно вопрос о литературе, да ее не так много(на русском языке) но она существует!(Предлагаю выкладывать и другую литературу, а также видеоматериалы, для лучшего ознакомления)

Пока выделил -
лекции В.Н.Крупского,
'Вычислительные машины и труднорешаемые задачи' М.Гэри, Д.Джонсона.

Все они легко находятся в интернете.Предлагаю участникам обсудить и вопрос литературы.

[Xaositect]

SuperIntegral! в сообщении #1061851 писал(а):

Итак, проблема равенства классов P NP. Рассмотрим пресловутое определение из википедии wiki:

Цитата:

Вопрос о равенстве классов сложности P и NP - одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.

Это не определение.

Цитата:

Предлагаю здесь начать обсуждение этой проблемы. Уверен многие пытались решать или думали о проблеме.
Как вы считаете, какой будет дан ответ на поставленный вопрос - они равны или нет?

Думаю, нет.

Цитата:

От себя, новичка, добавлю пару детских вопросов - Знаменитая задача коммивояжёра, вроде бы не считается NP полной, но при ограничениях существует ли маршрут не длиннее, чем некое заданное n она полной считается? Например, в книге Иэн Стюарта имеется такая фраза -

Цитата:

Задача о коммивояжере является «почти» NP-полной,но здесь есть одна техническая сложность: мы не знаем, относится ли она к классу NP.

Это серьезный ляп. Задача коммивояжера не может быть или не быть NP-полной, потому что NP-полнота определяется только для задач с ответом "да-нет". При исследовании задач оптимизации как раз и используется вариант "существует ли решение оптимальнее заданного".

Цитата:

Ну и традиционно вопрос о литературе, да ее не так много(на русском языке) но она существует!(Предлагаю выкладывать и другую литературу, а также видеоматериалы, для лучшего ознакомления)

Пока выделил - лекции В.Н.Крупского, 'Вычислительные машины и труднорешаемые задачи' М.Гэри, Д.Джонсона. Все они легко находятся в интернете.Предлагаю участникам обсудить и вопрос литературы.

Нет, можно сказать, что русской литературы нет. Например, мне не известно книг на русском языке, в которых излагался бы барьер релятивизации, буду рад оказаться неправ.

[whitefox]

SuperIntegral! в сообщении #1061851 писал(а):

Рассмотрим пресловутое определение из википедии wiki:

Цитата:

Вопрос о равенстве классов сложности P и NP - одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.

Э-э-э . . . определение чего?
Да и сам тезис, имхо, спорен. Что означает "теоретически возможно"? А что если доказательство равенства $\mathrm{P=NP}$ будет неконструктивным? И не будет никакой (даже теоретической) возможности доказать, что данный полиномиальный алгоритм решает интересующую нас NP-полную задачу? (Последнее возможно в силу теоремы Успенского-Райса)

SuperIntegral! в сообщении #1061851 писал(а):

Знаменитая задача коммивояжёра, вроде бы не считается NP полной, но при ограничениях существует ли маршрут не длиннее, чем некое заданное n она полной считается?

А что думают по этому поводу М.Гэри и Д.Джонсон? Или, хотя бы, Википедия?

-- 13 окт 2015, 09:56 --

Т.Кормен, Ч.Лейзерсон, Р.Ривест "Алгоритмы построение и анализ" Глава 36 NP-полнота.

[Vince Diesel]

Интересно, а какой консенсус у специалистов, верна гипотеза или не верна?

[Nemiroff]

У Скотта Ааронсона было: конечно же $\mathrm{P\neq NP}$, и тут либо я прав, либо я бог — а меня устраивает и то, и другое.

[Sender]

Vince Diesel в сообщении #1061951 писал(а):

Интересно, а какой консенсус у специалистов, верна гипотеза или не верна?

В вики пишут, что среди исследователей проводились опросы:

Цитата:

In a 2002 poll of 100 researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and therefore is impossible to prove or disprove.[6]

In 2012, 10 years later, the same poll was repeated. The number of researchers who answered was 151: 126 (83%) believed the answer to be no, 12 (9%) believed the answer is yes, 5 (3%) believed the question may be independent of the currently accepted axioms and therefore is impossible to prove or disprove, 8 (5%) said either don't know or don't care or don't want the answer to be yes nor the problem to be resolved

Количество оптимистов уверенно держится в районе 9%.

[SuperIntegral!]

Цитата:

А что если доказательство равенства $\mathrm{P=NP}$ будет неконструктивным? И не будет никакой (даже теоретической) возможности доказать, что данный полиномиальный алгоритм решает интересующую нас NP-полную задачу? (Последнее возможно в силу теоремы Успенского-Райса)

А может быть и методы решения не созданы еще?

Цитата:

SuperIntegral! в сообщении #1061851 писал(а):

Знаменитая задача коммивояжёра, вроде бы не считается NP полной, но при ограничениях существует ли маршрут не длиннее, чем некое заданное n она полной считается?

А что думают по этому поводу М.Гэри и Д.Джонсон? Или, хотя бы, Википедия?

Т.Кормен, Ч.Лейзерсон, Р.Ривест "Алгоритмы построение и анализ" Глава 36 NP-полнота.

В Алгоритмах - ‡Задача коммивояжера (ее оптимизационный вариант) является NP полной.

В дополнение к книгам - Существуют ли неразрешимые проблемы? Математика, сложность и вычисление . Серия Мир математики

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: обсуждение новых теорий не предвидится, а объяснений известных фактов - очень даже

[Xaositect]

SuperIntegral! в сообщении #1061960 писал(а):

В Алгоритмах - ‡Задача коммивояжера (ее оптимизационный вариант) является NP полной.

Нет, там тоже задача распознавания "существует ли путь длины меньше $k$". По крайней мере у меня во втором английском издании.

[whitefox]

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

По крайней мере у меня во втором английском издании.

В русском издании 1999 года тоже самое. Создаётся впечатление, что ТС читает по диагонали.

SuperIntegral, так какое мнение о TSP у Гэри с Джонсоном и у Википедии?

[Brukvalub]

(Оффтоп)

Вот такое начало темы:

SuperIntegral! в сообщении #1061851 писал(а):

Заголовок темы кричит сам за себя. Вы, форумчане, уже, наверно, догадались, что в этой теме будет идти речь о одной из самых сложных и великих трудностей в математике/информатике!

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

[Nemiroff]

(Оффтоп)

Brukvalub в сообщении #1062069 писал(а):

что читать ее и участвовать в обсуждении заведомо бессмысленно

Не, это с ТС заведомо бессмысленно обсуждать что-то. А между собой-то можно, если тут найдутся спецы/знатоки/сочувствующие/небезразличные. А ТС просто повод дал.

[SuperIntegral!]

Под оптимизационным вариантом я и имел в виду вариант "с существованием маршрута не длиннее k" (ошибочно)

Цитата из википедии:

Цитата:

Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач.

(Оффтоп)

Brukvalub, Я посему и предлагаю высказаться корифеем) А мы будем вникать и слушать) Тем более я не предлагаю никаких решений в духе - Найдено супер доказательство.

[whitefox]

С Википедией разобрались, а что говорят Гэри с Джонсоном?

[SuperIntegral!]

whitefox, а вот что:

Цитата:

Задача остается NP-полной ("существует ли маршрут длины не более $B$,проходящий через все города из $C$") даже в том случае, когда $d(C_i,C_j) \in\left\lbrace1,2\right\rbrace \forall C_i,C_j \in C$