Зачем нужно создавать проблемы как NP, так и P?

Question

Каково главное намерение или основное использование разделения любой проблемы на NP и P?Есть ли какая-то историческая причина для этого, или они создали эти концепции, чтобы помочь нам?Если да, то где они могут нам помочь?

Answer 1

Это слишком сложный вопрос, чтобы ожидать здесь исчерпывающего ответа, но, короче говоря, с практической точки зрения проблемы в P - это те проблемы, решение которых можно найти за разумное количество времени, а проблемы в NPте, для решения которых потребуется слишком много времени для вычисления (при условии P! = NP).

Границу между P и NP можно неофициально рассматривать как границу между проблемами, которые могут и не могут быть эффективно решены с помощью вычислений.

Вы должны начать с чтения Википедии http://en.wikipedia.org/wiki/P_versus_NP_problem, чтобы узнать больше о мотивации и целях этих классов сложности.

Answer 2

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

Здесь P будет относиться ко всем простым задачам (решаемым в разумные сроки).И NP сложные.(Разумного временного решения не существует, но, если вы можете угадать решение, его можно быстро проверить)

После того, как вы разбили проблемы на эти два набора, вы можете беспокоиться о решении.

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

С другой стороны, если это проблема P , вы можете беспокоиться о поиске более эффективного решения и т. д.

Answer 3

Я думаю, что "практическое" намерение разделения задач на P и NP является нижней границей.Если вы докажете, что проблема является NP-трудной (и вы согласны с распространенным мнением, что P! = NP), вы доказали, что не можете найти алгоритм для этой задачи, который выполняется в разумные сроки.

Более неофициально, скажем, ваш босс просит вас написать алгоритм, который работает за 5 минут.Если вы скажете, что не можете его найти, он подумает, что вы расслабляетесь.Если вы покажете ему, что он спрашивал вас о сложностях, он должен быть убежден, что вы не можете этого сделать. Возвращаясь к формализму, вы можете обосновать это с помощью алгоритма аппроксимации.

Это исторический разговор.потому что теперь в отрасли мы иногда реализуем задачи, которые являются NP-полными (например, SAT-решатели) или даже PSPACE-полными (например, формальная проверка, которая является PSPACE-полной по размеру формулы).С другой стороны, например, в графике, вы иногда не можете реализовать алгоритм, который работает в n^2.Даже nlogn иногда может быть резким.