Что такое проблемы NP?

Question

Я прочитал статью о Википедии, но не смогла понять, что именно проблема NP. Кто-нибудь может рассказать мне о них, а также что такое отношение к ним с проблемами?

Answer 1

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

Еще один важный пример из поля шифрования: Учитывая номер, который является результатом умножения двух очень больших простых чисел, очень трудно найти эти простые простыни, основанные только на результате. Однако, дано Два числа, очень легко проверить решение (умножьте их, сравните).

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

Answer 2

Не совсем ответ, потому что ссылка Piccolo более полезна, но исследователь HP утверждает, что имеет доказательство P! = NP, вот статья.

www.hpl.hp.com/personal/vinay_deolalikar/papers/pnp12pt.pdf

Это еще не было принято, но я желаю ему удачи в 1 млн.