Полиномиальный алгоритм

Полиномиальный алгоритм (Polinomial algorithm) — алгоритм, у которого временная сложность равна [math]\displaystyle{ \,O(p(n)), }[/math] где [math]\displaystyle{ \,p(n) }[/math] — некоторый полином.

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

См. также

• Задача о вершинном покрытии,
• Задача о выполнимости,
• Задача о клике,
• Задача о неэквивалентности регулярных выражений,
• Задача о разбиении,
• Задача о точном покрытии 3-множествами,
• Задача о трехмерном сочетании,
• Классы [math]\displaystyle{ \mathcal P }[/math] и [math]\displaystyle{ \mathcal NP }[/math],
• Метод локальной замены,
• Метод построения компонент,
• Метод сужения задачи,
• Полиномиальная сводимость (трансформируемость),
• [math]\displaystyle{ \mathcal NP }[/math]-полная задача,
• Труднорешаемая задача.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.