p-np

[terminator-101]

Я не могу врубится в сабж. Если исходить из этого вот примера из википедии

Цитата:

Например, верно ли, что среди чисел −2, −3, 15, 14, 7, −10, … есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.

Разница между p и np эквивалентна разнице между ответами на вопросы (решениями) "Есть ли вхождение X в множество" и "Есть ли взождения X и какие именно -- т.е. найти их все" Очевидно, что это не эквивалентные вычислительные задачи, смешно говорить о равенстве. Кажется, я неправильно понимаю проблему, либо пример некорректен. Объясните пожалуйста на пальцах, в чем тут подвох.

Повторная регистрация заблокированного участника. Заблокирован.
/ GAA, 18.10.2014

[Xaositect]

Не читайте википедию. Читайте, например, Гэри, Джонсон "Вычислительные машины и труднорешаемые задачи". Или Голдрайха "Computational Complexity: A Conceptual Perspective" по-английски.

Разница между P и NP как между "Верно ли, что данное подмножество суммируется в 0?" и "Верно ли, что какое-то подмножество суммируется в 0?"

[Евгений Машеров]

Приведенный Вами пример это не две задачи, одна из которых P, другая NP. Это пояснение, что такое класс NP. К классу P относятся задачи, решаемые за полиномиальное время. Есть задачи, для которых невозможность решить за полиномиальное время доказывается. Однако есть достаточно большой набор задач, некоторые из которых имеют важное прикладное значение, для которых полиномиальный алгоритм решения неизвестен, но проверить, что это решение, можно за полиномиальное время. Это позволяет надеяться, что существует и полиномиальный алгоритм их решения, и мы его просто ещё не придумали. В этом случае получится P=NP. Но возможно, что удастся доказать, что такой алгоритм невозможен. Тогда $P\neq NP$

[grizzly]

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