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