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:
Decision problems are important because any general problem with an nbit 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:
Compare with: satisfiability problem
Search Encyclopedia

Featured Article
