Английская Википедия:Exact algorithm

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality.

Unless P = NP, an exact algorithm for an NP-hard optimization problem cannot run in worst-case polynomial time. There has been extensive research on finding exact algorithms whose running time is exponential with a low base.[1] [2]

See also

References

Шаблон:Reflist