Editing Computational complexity theory (section)

===Problem instances===
A [[computational problem]] can be viewed as an infinite collection of ''instances'' together with a set (possibly empty) of ''solutions'' for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of [[primality testing]]. The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way, the ''instance'' is a particular input to the problem, and the ''solution'' is the output corresponding to the given input.

To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the [[travelling salesman problem]]: Is there a route of at most 2000 kilometres passing through all of Germany's 14 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in [[Milan]] whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.