Полиномиальный алгоритм: различия между версиями

'''Полиномиальный алгоритм''' (''Polinomial algorithm'') -

алгоритм, у которого ''временная сложность'' равна <math>O(p(n))</math>, где

<math>p(n)</math>--- некоторый полином.

Другое название --- ''Алгоритм полиномиальной временной сложности.''

См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами,

Задача о трехмерном сочетании, Классы <math>\cal P</math> и <math>\cal NP</math>, Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), <math>\cal NP</math>-полная задача, Труднорешаемая задача.''

[Ахо-Хопкрофт-Ульман],

[Касьянов/88],

[Евстигнеев-Касьянов/94],

[Касьянов/95]