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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Полиномиальный алгоритм''' (''Polinomial algorithm'') - алгоритм, у которого ''временна...)
 
Нет описания правки
Строка 1: Строка 1:
'''Полиномиальный алгоритм''' (''Polinomial algorithm'') -  
'''Полиномиальный алгоритм''' (''[[Polinomial algorithm]]'') -  
алгоритм, у которого ''временная сложность'' равна <math>O(p(n))</math>, где
[[алгоритм]], у которого ''[[временная сложность]]'' равна <math>O(p(n))</math>, где
<math>p(n)</math>--- некоторый полином.
<math>p(n)</math>--- некоторый полином.


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


См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами,
==См. также ==''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Метод локальной замены]], [[Метод построения компонент]], [[Метод сужения задачи]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-Полная задача|<math>\mathcal NP</math>-полная задача]], [[Труднорешаемая задача]].''
Задача о трехмерном сочетании, Классы <math>\cal P</math> и <math>\cal NP</math>, Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), <math>\cal NP</math>-полная задача, Труднорешаемая задача.''
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],
[Ахо-Хопкрофт-Ульман],

Навигация