flâneur

Decision problem

en.wikipedia.org · 1,914 words · saved by 1 readers

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called decidable.

Decision problem - Wikipedia Jump to content From Wikipedia, the free encyclopedia Yes/no problem in computer science This article is about decision problems in complexity theory. For the decision problem in formal logic, see Entscheidungsproblem . For analysis of the process of making choices, see Decision theory . A decision problem has only two possible outputs ( YES or NO ) on any input. In computability theory and computational complexity theory , a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem

saved by

related reading