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

[whitefox]

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

[Deggial]

Вопрос Myhailo отделён

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

SuperIntegral!
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Jukier]

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

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

Кроме вышеприведенных могу посоветовать:
1. Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений.
2. Лекции Э. А. Гирша по теории сложности.
3. Лекции Oded Goldreich (ищутся по Complexity theory).

Насчет равенства классов: думаю, что нет.

Эта тема много раз обсуждалась на множестве форумов, вряд ли здесь можно высказать что-то новое.

[SuperIntegral!]

Обнаружил для себя интересную страничку, возможно, кто-то тоже откроет ее для себя.

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Если кратко, то на страничке описаны многочисленные попытки доказательства $P = NP$ или $P \ne NP$
Преобладают версии $P = NP$

[Mihaylo]

Безуспешная попытка доказать P=NP:
Рассмотрим задачу SAT с булевыми переменными $x_1, x_2, ..., x_n$, булева функция $y=f(x_1, x_2, ..., x_{n-1}, x_n)$ должна быть равна 1. Рассмотрим две подзадачи $f(x_1, x_2, ..., x_{n-1}, 0)=1$, $f(x_1, x_2, ..., x_{n-1}, 1)=1$, в которых отсутствует переменная $x_n$. Таким образом, если научиться решать другую задачу $g(x_1, x_2, ..., x_{n-1})=1$, содержащую $(n-1)$ переменных, то так же быстро можно решить и исходную задачу. По математической индукции приходим к тому, что $n$-арная функция решается также быстро как и унарная функция. Унарная функция решается очень быстро.

Подвох в доказательстве: $n$-арная задача на самом деле сводится к $2^n$ унарных задачам, то есть полиномиальная сводимость отсутствует.

На самом деле, на мой взгляд, это доказательство свидетельствует об обратном, что $P\ne NP$. Рассматриваемые в доказательстве задачи эквивалентны, но так как каждая из $2^n$ унарных задач не совсем тривиальна, то значит и задачу SAT нельзя быстро решить. Достаточно доказать, что задачи эквивалентны (что я еще не сделал).

[whitefox]

Статья от автора проблемы.

[SuperIntegral!]

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

[whitefox]

Полиномиальный алгоритм решающий какую-либо NP-полную задачу будет вполне себе конструктивным доказательство равенства $\mathrm{P=NP}.$ А Вы подумали о чём-то другом?

[SuperIntegral!]

Да нет в принципе. Возможно, что доказав некую причастность классов (ведь кроме $P$ и $NP$ их много) можно доказать и саму проблему..

Но алгоритм выглядит куда интереснее!

[Mihaylo]

Реально короткое доказательство $P\ne NP$ от Hubert Chen (2003)

Цитата:

Proof by contradiction. Assume $P = NP$. Let $y$ be a proof that $P = NP$. The proof $y$ can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since $P = NP$, the proof $y$ can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction.

[whitefox]

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

Возможно, что доказав некую причастность классов (ведь кроме $P$ и $NP$ их много) можно доказать и саму проблему..

А вот такое доказательство будет как раз таки неконструктивным. Ибо, доказав равенство $\mathrm{P=NP},$ мы, скорее всего, не сможем предъявить алгоритма решающего какую-нибудь NP-полную задачу за полиномиальное время.

[Mihaylo]

На мой взгляд, проблему $P ? NP$ следует решать постановкой следующего вопроса:
Почему некоторые алгоритмы распознавания свойств полиномиальные?

Другая формулировка:
Почему существуют задачи класса $P$?

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

[arseniiv]

(Оффтоп)

Не $?$, а $\stackrel?=$ лучше: $\mathrm P \stackrel?= \mathrm{NP}$.

Mihaylo в сообщении #1063967 писал(а):

Почему существуют задачи класса $P$? <…> Странно, что в них особого?

А почему существуют полиномы и что в них такого особого?

[Mihaylo]

(Оффтоп)

arseniiv
А почему Вы привязались к полиномам вообще? Ведь можно было сказать, почему некоторые алгоритмы быстрые/эффективные? Какие свойства у задач, решаемых быстро?