Decision problem

In computer science a decision problem is a set of related problem instances, such that every problem instance requires a YES/NO answer. A typical example of a decision problem is the question: "Is a given integer prime?" One instance of this decision problem would be "Is 17 prime?".

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:

• 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.
• The strings that describe a set of integers such that a subset of them has the sum 0.
• The strings that describe a Turing machine and an input tape of this machine such that the Turing machine halts on this input.

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:

Given an input X, return the answer string Y

then the associated decision problem is:

Given an input X and an integer k, return whether the kth bit of Y is 1

---

/Talk