Каковы проблемы НП?
Я читал статью в Википедии, но не мог понять, в чем именно заключаются проблемы NP. Может ли кто-нибудь рассказать мне о них, а также о том, как они связаны с проблемами P?
2 ответа:
NP задачи - это задачи, которые при заданном предлагаемом решении можно проверить решение за полиномиальное время. Например, если у вас есть список университетских курсов и вам нужно создать расписание, чтобы курсы не конфликтовали, это будет действительно трудная задача (по сложности). Тем не менее, учитывая предложенный график, вы можете легко проверить его правильность.
Еще один важный пример из области шифрования: дано число, которое является результатом умножения двух очень большие простые числа, очень трудно найти эти простые числа, основанные только на результате. Тем не менее, учитывая два числа, очень легко проверить решение (умножить их, сравнить).
Я намеренно выбрал примеры, которые находятся в NP, а не в P (т. е. проблема, для которой трудно найти решение), чтобы вы могли понять разницу. Все проблемы, которые легко решить, также легко проверить - просто решить и сравнить. То есть P-подмножество NP.
Не совсем ответ, потому что ссылка Пикколо более полезна, но исследователь HP утверждает, что доказал P != NP, вот бумага.
Www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
Он еще не был принят, но я желаю ему удачи за 1 миллион долларов.