2.2.1. Полиномиальность и эффективность

Определение 11. Алгоритм называется полиномиальным, если его сложность t(n) в наихудшем случае ограничена сверху некоторым полиномом (многочленом) от n.

В теории алгоритмов в основном рассматриваются переборные или «распознавательные» (задачи, решение которых сводится к получению ответа «да» или «нет») массовые задачи. Произвольные задачи обычно легко сводятся к переборным или «распознавательным» задачам.

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

Может ли неполиномиальный алгоритм быть эффективным? Ответ утвердительный.

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

Подчеркнем, что примеров задач, на которых нарушается основополагающее равенство

«полиномиальность»=«эффективность»

крайне мало по сравнению с числом примеров, на которых оно блестяще подтверждается.

Класс всех переборных задач с полиномиальной сложностью обозначается P.

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

С другой стороны, алгоритмическая задача называется труднорешаемой (NP-полной), если для нее не существует полиномиального алгоритма.

По этой причине задачи решаемые с экспоненциальной сложность относя к классу NP-полных задач.

Историю современной теории сложности вычислений принято отсчитывать с работ С.А.Кука (1975 года), в которых были заложены основы теории NP-полноты и доказано существование вначале одной, а затем достаточно большого числа (а именно, 21) естественных NP-полных задач. К 1979 году было известно уже более 300 наименований. К настоящему времени количество известных NP-полных задач выражается четырехзначным числом, и постоянно появляются новые, возникающие как в самой математике и теории сложности, так и в таких дисциплинах, как биология, социология, военное дело, теория расписаний, теория игр и т.д.

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

Одним из наиболее важных исключений являются задачи типа дискретного логарифма и факторизации, на которых основаны многие современные криптопротоколы.

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