Один из важнейших вопросов Computer Science, на который до сих пор не получен ответ: является ли NP собственным надмножеством P? Существуют ли задачи, которые относятся к NP, но не принадлежат P, или это одно и то же множество задач? Другими словами: любая ли задача, решение которой быстро проверяется компьютером, также быстро решается компьютером? Большинство специалистов в области Computer Science считают, что P ≠ NP, но никаких математических доказательств найдено не было26 (рис. 3.1).
Гид по Computer Science
·
Вильям Спрингер
