|
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some 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. For example, the problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?" is a decision problem. The answer can be either 'yes' or 'no', and depends 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'', given ''x'' and ''y''. One such algorithm is long division, taught to many school children. If the remainder is zero the answer produced is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm, such as this example, is called ''decidable''. The field of computational complexity categorizes ''decidable'' decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of recursion theory, meanwhile, categorizes ''undecidable'' decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution. Decision problems are closely related to function problems, which can have answers that are more complex than a simple 'yes' or 'no'. A corresponding function problem is "given two numbers ''x'' and ''y'', what is ''x'' divided by ''y''?". They are also related to optimization problems, which are concerned with finding the ''best'' answer to a particular problem. There are standard techniques for transforming function and optimization problems into decision problems, and vice versa, that do not significantly change the computational difficulty of these problems. For this reason, research in computability theory and complexity theory have typically focused on decision problems. ==Definition== A ''decision problem'' is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns ''yes''. These inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet or over some other finite set of symbols. The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined in this way as formal languages. Alternatively, using an encoding such as Gödel numberings, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Decision problem」の詳細全文を読む スポンサード リンク
|