P! = NP вопрос

Question

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

Относительно проблемы P NP, этот отрывок из http://en.wikipedia.org/wiki/P_versus_NP_problem: «По сути, вопрос P = NP? Спрашивает: Предположим, что ответы« да »или« нет »можно быстро проверить. Сами ответы тоже быстро вычисляются? "

Мне интересно, как скорость проверки ответа связана со скоростью генерации решения?

Answer 1

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

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

Интуитивно понятно, что ответ «нет» (то есть P! = NP).Как мы можем симулировать бесконечный параллелизм?Это то, во что верит почти каждый эксперт.Но как это доказать, и загадка, которая стоит 1 000 000 долларов призовых.

Answer 2

По существу, во множестве задач NP или недетерминированного полиномиального времени ответ может быть проверен за полиномиальное время.Вопрос заключается в том, могут ли все такие проблемы быть определены за полиномиальное время * 1002. *

Если P = NP истинно, и в таких алгоритмах обнаружено много проблем, которые трудно решить, но легко проверитьрешение, такое как доказательства, становится таким же простым, как и для проверки.

Answer 3

Давайте предположим, что волшебник передал мне решение «сложной» проблемы, и я могу легко проверить, является ли это решение правильным или нет.НО, я могу легко вычислить это решение самостоятельно?(полиномиальное время)

Это как раз вопрос.

Answer 4

Эта проблема была решена сегодня!

(Возможно.)

Answer 5

Может быть или не быть связанным.

Людям небезразличны проблемы НП, потому что мы хотим решать их быстро и постоянно, но до сих пор мы не нашли способа их быстро решить. Мы хотим знать, есть ли быстрый способ их решить или мы должны отказаться от попыток.

Answer 6

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

Answer 7

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

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

Основной факт вычислительной сложности состоит в том, что NP эквивалентен классу языков, проблемы проверки которых находятся в P.На самом деле, NP иногда определяется как этот класс;оба определения взаимозаменяемы, и определение проверки имеет прямое отношение к компьютерам, подобным детерминированным машинам Тьюринга, в реальном мире.

Таким образом, NP - это класс проблем, которые можно проверить вpoly-time на «реальной» машине и разрешимый в poly-time на очень похожей теоретической машине.Таким образом, вопросы разрешимости и проверяемости связаны.

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

Answer 8

Являются ли они родственниками или нет, это одна из «Проблем Миллениума» Фонда Клэйпул, и они дадут миллион долларов кому-либо, предоставив соответствующее доказательство, которое выдержит несколько лет интенсивного исследования.

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

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

Другая проблема - это влияние, которое это может оказать. В настоящее время мало кто верит, что существует эффективный метод решения NP-полных задач, поэтому открытие того, что P! = NP, окажет незначительное практическое влияние. Открытие эффективного способа решения NP-завершенных задач революционизирует многие компьютерные науки. Это значительно упростит многие вещи и разрушит криптографию, как мы ее знаем, упрощая дешифрование.