Это очень неформальный ответ на заданный вопрос.

Может ли число 3233 быть записано как произведение двух других чисел больше 1 ? Есть ли способ обойти все Семь мостов Кенигсберга , не переходя ни один мост дважды? Это примеры вопросов, которые имеют общую черту. Может быть неочевидно, как эффективно определить ответ, но если ответ «да», затем есть короткое и быстрое доказательство. В первом случае нетривиальная факторизация 51; во втором - маршрут перехода по мостам (соответствие ограничениям).

проблема принятия решения - это набор вопросов с ответами «да» или «нет», которые различаются только по одному параметру. Скажите, что задача COMPOSITE = {"Является ли n составным": n является целым числом} или EULERPATH = {"Имеет ли граф G путь Эйлера?" : G - конечный граф}.

Теперь некоторые проблемы решения поддаются эффективным, если не очевидным алгоритмам. Эйлер открыл эффективный алгоритм для решения таких задач, как «Семь мостов Кенигсберга» более 250 лет назад.

С другой стороны, для многих проблем, связанных с решением, это ' Не очевидно, как получить ответ, но если вы знаете дополнительную информацию, очевидно, как доказать, что вы получили правильный ответ. КОМПОЗИТ выглядит следующим образом: Пробное деление - очевидный алгоритм, и он медленный: чтобы разложить на множители 10-значное число, вам нужно попробовать что-то вроде 100 000 возможных делителей. Но если, например, кто-то сказал вам, что 61 является делителем 3233, простое деление в столбик - эффективный способ убедиться, что они верны.

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

Исследование алгоритмов продолжается, и постоянно создаются новые умные алгоритмы. Проблема, которую вы, возможно, не знаете, как эффективно решить сегодня, может иметь эффективное (если не очевидное) решение завтра. Фактически, исследователям понадобилось до 2002 , чтобы найти эффективное решение для КОМПОЗИТА! При всех этих достижениях действительно стоит задаться вопросом: не является ли этот рассказ о коротких доказательствах всего лишь иллюзией? Может быть каждая проблема решения, которая поддается эффективным доказательствам, имеет эффективное решение? Никто не знает .

Возможно, самый большой вклад в эту область был внесен с открытием особого класса проблем NP. Играя с моделями схем для вычислений, Стивен Кук обнаружил проблему решения для разновидности NP, которая была доказуемо такой же или более сложной, чем каждая другая проблема NP. Эффективное решение проблемы логической выполнимости может быть использовано для создания эффективного решения любой другой проблемы в NP. Вскоре после этого Ричард Карп показал, что ряд других проблем, связанных с принятием решений, может служить той же цели. Эти проблемы, в некотором смысле «самые сложные» проблемы в NP, стали известны как NP-полные проблемы.

Конечно, NP - это только класс задач решения. Многие проблемы не сформулированы естественным образом таким образом: «найти множители N», «найти кратчайший путь в графе G, который посещает каждую вершину», «дать набор назначений переменных, который делает следующее логическое выражение истинным». Хотя можно неформально говорить о том, что некоторые такие проблемы находятся «в NP», технически это не имеет большого смысла - это не проблемы решения. Некоторые из этих проблем могут даже иметь такую ​​же мощность, как NP-полная проблема: эффективное решение этих проблем (без решения) привело бы непосредственно к эффективному решению любой NP-проблемы. Подобная проблема называется NP-сложной .

Проблемы NP-complete - это проблемы, которые являются одновременно NP-Hard и в классе сложности NP. Следовательно, чтобы показать, что любая заданная проблема является NP-полной, вам нужно показать, что проблема как в NP, так и в том, что она NP-трудна.

полиномиальное время и возможное решение (т. е. сертификат) проблемы в NP могут быть проверены на правильность за полиномиальное время.

Пример недетерминированного решения проблемы k-клик может выглядеть примерно так:

1) случайным образом выбрать k узлов из графа

2) проверить, что эти k узлов образуют клику.

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

Обратите внимание, что все проблемы, детерминированно разрешимые за полиномиальное время, также находятся в NP.

Показ того, что проблема NP-сложная, обычно включает в себя редукцию от какой-то другой NP-сложной проблемы к вашей проблеме с использованием отображения полиномиального времени: http://en.wikipedia.org/wiki/Reduction_ (сложность)