In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
and
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
, exact algorithms are
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s that always solve an optimization problem to optimality.
Unless
P = NP
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used above ...
, 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.
See also
*
Approximation-preserving reduction
In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the dista ...
*
APX is the class of problems with some constant-factor approximation algorithm
*
Heuristic algorithm
In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or whe ...
*
PTAS - a type of approximation algorithm that takes the approximation ratio as a parameter
References
{{reflist
Computational complexity theory
Optimization algorithms and methods