Editing Computational complexity theory (section)

==Computational problems==
[[Image:TSP Deutschland 3.png|thumb|upright=1.5|A traveling salesman tour through 14 German cities]]

===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.

===Representing problem instances===
When considering computational problems, a problem instance is a [[string (computer science)|string]] over an [[Alphabet (computer science)|alphabet]]. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are [[bitstring]]s. As in a real-world [[computer]], mathematical objects other than bitstrings must be suitably encoded. For example, [[integer]]s can be represented in [[binary notation]], and [[graph (discrete mathematics)|graph]]s can be encoded directly via their [[adjacency matrix|adjacency matrices]], or by encoding their [[adjacency list]]s in binary.

Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.

===Decision problems as formal languages===
[[Image:Decision Problem.svg|thumb|A [[decision problem]] has only two possible outputs, ''yes'' or ''no'' (or alternately 1 or 0) on any input.]]
[[Decision problem]]s are one of the central objects of study in computational complexity theory. A decision problem is a type of computational problem where the answer is either ''yes'' or ''no'' (alternatively, 1 or 0). A decision problem can be viewed as a [[formal language]], where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an [[algorithm]], whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer ''yes'', the algorithm is said to accept the input string, otherwise it is said to reject the input.

An example of a decision problem is the following. The input is an arbitrary [[graph (discrete mathematics)|graph]]. The problem consists in deciding whether the given graph is [[connectivity (graph theory)|connected]] or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.

===Function problems===
A [[function problem]] is a computational problem where a single output (of a [[total function]]) is expected for every input, but the output is more complex than that of a [[decision problem]]—that is, the output is not just yes or no. Notable examples include the [[traveling salesman problem]] and the [[integer factorization problem]].

It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples <math>(a, b, c)</math> such that the relation <math>a \times b = c</math> holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.

===Measuring the size of an instance===
To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. The input size is typically measured in bits. Complexity theory studies how algorithms scale as input size increases. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with <math>2n</math> vertices compared to the time taken for a graph with <math>n</math> vertices?

If the input size is <math>n</math>, the time taken can be expressed as a function of <math>n</math>. Since the time taken on different inputs of the same size can be different, the worst-case time complexity <math>T(n)</math> is defined to be the maximum time taken over all inputs of size <math>n</math>. If <math>T(n)</math> is a polynomial in <math>n</math>, then the algorithm is said to be a [[polynomial time]] algorithm. [[Cobham's thesis]] argues that a problem can be solved with a feasible amount of resources if it admits a polynomial-time algorithm.