* The strings over {'a', 'b'} that conists of alternating a's and b's. * The strings over {'a', 'b'} that contain an equal amount of a's and b's. * The strings that describe a graph with edges labeled with natural numbers indicating their length, and and a path in that graph such that it is the shortes path between its begin and end node. |
* The strings over {a, b} that conists of alternating a's and b's. * The strings over {a, b} that contain an equal amount of a's and b's. * The strings that describe a graph with edges labeled with natural numbers indicating their length, two vertices of the graph, and a path in the graph which is the shortest path between the two vertices. |
A decision problem is usually formalized as the problem of deciding whether a given string belongs to some specified set of strings, also called a formal language. The above prime decision problem could be formalized as the language of all those strings over the alphabet {0, 1} which describe the binary expansion of a prime number.
If there is an algorithm that is able to correctly decide for every possible input string whether it belongs to the language, then the problem is called decidable and otherwise it is called undecidable. In complexity theory it is studied how much time and space (memory) the decidable decision problems require.
Some examples of decision problems expressed as langugaes are:
Decision problems are important because any general problem with an n-bit answer can be transformed into a decision problem with a YES/NO answer, and vice versa. Solving either can't be more than n times harder than solving the other. There are several ways to do this transform. For example, if the general problem is of the form: