Decision problem

In the theory of computation a problem is a set of finite-length questions (strings) with associated finite-length answers (strings). A decision problem is a problem where all the answers are YES or NO. 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 set contains exactly those questions whose answers were "YES". The above prime decision problem could be formalized as the language of all those strings over the alphabet {0, 1} which are the binary representation 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. If there is an algorithm that can always answer "YES" when the string is in the language, but runs forever without halting when it isn't in the language, then the language is partially decidable. In computability theory, it is studied which languages are decidable using algorithms with various restrictions. In complexity theory it is studied how many resources (time, memory, parallel processors, etc.) the decidable decision problems require.

Some examples of decision problems expressed as languages are:

• The strings over {a, b} that consists 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. Solving the general problem can't be more than n times harder than solving the decision problem. 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

Compare with: satisfiability problem