P! = вопрос о NP
Не 'чистый' вопрос о программировании, но так как это глубоко вовлечено в программирование теории, я думал, что это лучше всего спросило здесь.
Относительно проблемы NP P, этой выборки из http://en.wikipedia.org/wiki/P_versus_NP_problem: "В сущности, вопрос P = NP? спрашивает: Предположим, что да отвечают на вопрос "да" или "нет", может быть проверен быстро. Затем могут сами ответы также быть вычисленными быстро?"
Меня оставляют, задаваясь вопросом, как скорость проверки является ответом, связанным со скоростью генерации решения?
8 ответов
По сути, в наборе задач NP или недетерминированного полиномиального времени ответ можно проверить за полиномиальное время. Вопрос в том, могут ли все такие проблемы быть решены за полиномиальное время.
Если P = NP истинно, и такие алгоритмы обнаруживаются, многие проблемы, которые трудно решить, но легко проверить, решение, например доказательства, становятся так же легко решить, как и проверить.
Предположим, у вас огромный параллелизм - сколько бы вы ни хотели. Затем вы можете одновременно сгенерировать все возможные решения, проверить, какие из них были правильными, и вывести правильное решение. При наличии бесконечного параллелизма это метод генерации решения. Набор задач в NP - это те, для которых эта процедура будет работать быстро, потому что единственный интересный вычислительный шаг, который она выполняет, - это проверка правильности решений, а это может быть эффективно выполнено для задач в NP. Обратите внимание, что для некоторых других проблем даже этот параллелизм не позволит нам быстро находить решения, поскольку требует, чтобы проверка решений была простой.
Но у нас нет бесконечного параллелизма. Можем ли мы как-то смоделировать это с полиномиальными накладными расходами? Если это так, мы могли бы представить себе выполнение описанной выше процедуры и эффективное нахождение решений для каждой проблемы, для которой проверка была простой. Это вопрос P vs. NP.
Интуитивно кажется очевидным, что ответ - «нет» (т.е. P! = NP). Как мы могли смоделировать бесконечный параллелизм? Так считает практически каждый специалист. Но как это доказать - загадка, и она стоит 1000000 долларов призовых.
Предположим, мне передал фокусник решение "сложной" проблемы, и я могу легко проверить, правильное это решение или нет. НО, могу ли я легко вычислить это решение? (полиномиальное время)
Это как раз вопрос.
Это может быть связано, а может и не быть.
Людей волнуют проблемы NP, потому что мы хотим решать их быстро и постоянно, но пока мы не нашли способа решить их быстро. Мы хотим знать, есть ли быстрый способ их решить или стоит отказаться от попыток.
P - это класс всех языков, которые могут быть вычислены за полиномиальное время с помощью детерминированной машины Тьюринга. Современный компьютер очень похож на детерминированную машину Тьюринга, за исключением того, что машина Тьюринга, по сути, имеет бесконечную память. Это различие обычно игнорируется в практических целях.
NP - это класс всех языков, которые могут быть вычислены за полиномиальное время на не -детерминированном токарном станке. Недетерминированная машина Тьюринга не соответствует никакому реальному устройству.
Основной факт вычислительной сложности состоит в том, что NP эквивалентен классу языков, проблемы проверки которых находятся в P . Фактически, NP иногда определяется как этот класс; эти два определения взаимозаменяемы, а определение верификации имеет то преимущество, что оно имеет прямое отношение к детерминированным компьютерам, подобным машине Тьюринга, в реальном мире.
Итак NP - это класс задач, которые можно проверить в поливремени на «реальной» машине и решить за поливремени на очень похожей теоретической машине. Таким образом, вопросы разрешимости и проверяемости взаимосвязаны.
Сейчас большинство компьютерных ученых считают, что P и NP не эквивалентны; то есть, что существуют языки, вычислимые в поливремени с помощью недетерминированной машины Тьюринга, но не с помощью детерминированной машины Тьюринга, или, что то же самое, которые не могут быть решены в поливремени с помощью детерминированной машины Тьюринга, но чьи решения могут быть проверены в поливремени. с помощью детерминированной машины Тьюринга.
Здесь нет прямого отношения. Может возникнуть интуитивное ощущение, что проверить ответ проще, чем выработать ответ, поскольку часть любого поколения должна гарантировать, что ответ правильный. Таким образом, можно использовать метод грубой силы, чтобы попробовать разные решения, но это имеет тенденцию приводить к экспоненциальным сложностям, выходящим за пределы P, или примерно это то, что я помню из класса Complexity много лет назад.
Родственники они или нет - это одна из "Проблем тысячелетия" Фонда Клэйпула, и они передадут миллион долларов тому, кто предоставит соответствующее доказательство, которое выдержит менее нескольких лет тщательное обследование.
Типы вопросов больше связаны, чем кажется, поскольку другое определение проблемы NP - это такое, которое может быть эффективно решено с помощью произвольно параллельного компьютера.
Что действительно интересует людей, так это отсутствие доказательств. Есть доказательства для похожих вопросов, но не этого. Это заинтриговывает людей, особенно математиков, поскольку доказательство, вероятно, поможет лучше понять другие вещи. Очевидно, именно так и обстоит дело с доказательством Перельманом гипотезы Пуанкаре, еще одной проблемы тысячелетия.
Еще одна проблема - это то, какое влияние это могло иметь. В настоящий момент мало кто верит, что существует эффективный метод решения NP-полных задач, поэтому открытие того, что P! = NP не имело бы большого практического значения. Открытие эффективного способа решения NP-полных задач произвело бы революцию в компьютерных науках. Это упростило бы многие вещи и разрушило бы криптографию в том виде, в каком мы ее знаем, упростив расшифровку.