Editing Decision problem (section)

==Optimization problems==
{{main|Optimization problem}}

Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the ''best'' answer to a particular input.  Optimization problems arise naturally in many applications, such as the [[traveling salesman problem]] and many questions in [[linear programming]].

Function and optimization problems are often transformed into decision problems by considering the question of whether the output is ''equal to'' or ''less than or equal to'' a given value. This allows the complexity of the corresponding decision problem to be studied; and in many cases the original function or optimization problem can be solved by solving its corresponding decision problem. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each ''N'', to decide whether the graph has any tour with weight less than ''N''.  By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.

Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as [[operations research]].