Для предоставления самого простого ответа, я могу думать:

предположим у нас есть проблема, которая берет определенное число исходных данных и имеет различные потенциальные решения, которые могут или не могут решить проблему для данных исходных данных. Логическая загадка в журнале загадки была бы хорошим примером: исходные данные являются условиями ("George, не живет в синем или зеленом доме"), и потенциальное решение является списком операторов ("жизни George в желтом доме, выращивает горох и владеет собакой"). Известным примером является проблема Коммивояжера: учитывая список городов, и времена для получения от любого города до любого другого и ограничения по времени потенциальное решение было бы списком городов в порядке, продавец посещает их, и это работало бы, если бы сумма времени прохождения была меньше, чем ограничение по времени.

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

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

Поэтому проблема P=NP может быть выражена этот путь: Если можно проверить решение для проблемы вида, описанного выше эффективно, можно ли найти решение (или доказать ли, что нет ни одного), эффективно? Очевидный ответ, "Почему необходимо быть в состоянии?", и это в значительной степени, где вопрос стоит сегодня. Никто не был в состоянии доказать его так или иначе, и это беспокоит много математиков и программистов. Вот почему кто-либо, кто может доказать решение, подлежит миллиону долларов от Основы Claypool.

Мы обычно предполагаем, что P не равняется NP, что нет никакого общего способа найти решения. Если оказалось, что P=NP, много вещей изменится. Например, криптография стала бы невозможной, и с ним любой вид конфиденциальности или verifiability в Интернете. В конце концов, мы можем эффективно взять зашифрованный текст и ключ и произвести оригинальный текст, поэтому если P=NP мы могли бы эффективно найти ключ, не зная это заранее. Взламывание пароля стало бы тривиальным. С другой стороны, существуют целые классы планирования проблем и проблем распределения ресурсов, которые мы могли решить эффективно.

Вы, возможно, услышали полное NP описание. Полной NP проблемой является та, которая является NP (конечно), и имеет это интересное свойство: если это находится в P, каждая проблема NP, и таким образом, P=NP. Если Вы могли бы найти способ эффективно решить проблему Коммивояжера или логические загадки из журналов загадки, Вы могли эффективно решить что-либо в NP. Полная NP проблема, в некотором смысле, самый твердый вид проблемы NP.

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

Краткое изложение от моего скромного знания:

существуют некоторые легкие вычислительные проблемы (как нахождение кратчайшего пути между двумя точками в графике), который может быть вычислен довольно быстро (O (n^k), где n является размером входа, и k является константой (в случае графиков, это - количество вершин или краев)).

Другие проблемы, как нахождение пути, который пересекает каждую вершину в графике или получении закрытого ключа RSA от открытого ключа, более трудны (O (e^n)).

, Но CS говорят, говорит, что проблема состоит в том, что мы не можем 'преобразовать' недетерминированную Машину Тьюринга в детерминированную, мы можем, однако, преобразовать недетерминированные конечные автоматы (как regex синтаксический анализатор) в детерминированные (хорошо, Вы можете, но время выполнения машины займет много времени). Таким образом, мы должны попробовать каждый возможный путь (обычно умные преподаватели CS могут исключить несколько).

Это интересно, потому что ни у кого даже нет идеи решения. Некоторые говорят, что это верно, некоторые говорят, что это - ложь, но нет никакого согласия. Другая интересная вещь состоит в том, что решение было бы вредно для общественности/шифрований с закрытым ключом (как RSA). Вы могли повредить их так же легко, как генерация ключа RSA теперь.

И это - довольно вдохновляющая проблема.

Нет очень, я могу добавить к какой и почему из P =? Часть NP вопроса, но в отношении доказательства. Мало того, что доказательство стоило бы некоторый дополнительный кредит, но это решит один из проблемы Тысячелетия . Интересный опрос был недавно проведен и , опубликованные результаты (PDF) определенно стоит считать в отношении предмета доказательства.

Во-первых, некоторые определения:

• А конкретная проблема находится в P, если можно вычислить решение вовремя меньше чем n^k приблизительно для k, где n размер входа. Например, сортировка может быть сделана в n log n, который является меньше чем n^2, таким образом сортируя являются полиномиальным временем.

• проблема А находится в NP, если там существует k таким образом, что там существует решение размера самое большее n^k, который можно проверить вовремя самое большее n^k. Возьмите с 3 окрасками из графиков: учитывая график, с 3 окрасками является список (вершина, цвет) пары, который имеет размер O(n), и можно проверить вовремя O(m) (или O(n^2)), есть ли у всех соседей различные цвета. Таким образом, график является 3-поддающимся окраске, только если существует короткое и с готовностью решение поддающееся проверке.

эквивалентным определением NP являются "проблемы, разрешимые машина Тьюринга N ondeterministic в [1 118] время P olynomial". В то время как это говорит Вам, куда название происходит от, оно не дает Вам то же интуитивное чувство того, на что похожи проблемы NP.