# Exact algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Exact_algorithm
> Markdown URL: https://mediated.wiki/source/Exact_algorithm.md
> Source: https://en.wikipedia.org/wiki/Exact_algorithm
> Source revision: 962596137
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computer science](/source/computer_science) and [operations research](/source/operations_research), '''exact algorithms''' are [algorithm](/source/algorithm)s that always solve an optimization problem to optimality.

Unless [P = NP](/source/P_%3D_NP), an exact algorithm for an [NP-hard](/source/NP-hardness) optimization problem cannot run in worst-case [polynomial time](/source/polynomial_time). There has been extensive research on finding exact algorithms whose running time is exponential with a low base.<ref>{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Kaski | first2 = Petteri
 | date = March 2013
 | doi = 10.1145/2428556.2428575
 | issue = 3
 | journal = [Communications of the ACM](/source/Communications_of_the_ACM)
 | pages = 80–88
 | title = Exact Exponential Algorithms
 | url = http://cacm.acm.org/magazines/2013/3/161189-exact-exponential-algorithms/fulltext
 | volume = 56}}.</ref>
<ref>{{cite book
|last1=Fomin|first1=Fedor V.
|last2=Kratsch|first2=Dieter
|title=Exact Exponential Algorithms
|url=https://archive.org/details/exactexponential00fvfo|url-access=limited|publisher=Springer
|year=2010
|isbn=978-3-642-16532-0
|page=[https://archive.org/details/exactexponential00fvfo/page/n217 203]
}}</ref>

== See also ==
* [Approximation-preserving reduction](/source/Approximation-preserving_reduction)
* [APX](/source/APX) is the class of problems with some constant-factor approximation algorithm
* [Heuristic algorithm](/source/Heuristic_algorithm)
* [PTAS](/source/Polynomial-time_approximation_scheme) - a type of approximation algorithm that takes the approximation ratio as a parameter

==References==
{{reflist}}

Category:Computational complexity theory
Category:Optimization algorithms and methods

---
Adapted from the Wikipedia article [Exact algorithm](https://en.wikipedia.org/wiki/Exact_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Exact_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.