Decison problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
A decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input.

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. The answer is dependent on the values of the input parameters. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set. Some of the most important problems in mathematics are undecidable.