Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Decision_problem> ?p ?o. }
Showing items 1 to 41 of
41
with 100 items per page.
- Decision_problem abstract "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. 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.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.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.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.Research in computability theory has typically focused on decision problems. As explained in the section Equivalence with function problems below, there is no loss of generality.".
- Decision_problem thumbnail Decision_Problem.svg?width=300.
- Decision_problem wikiPageExternalLink Search_Problems_and_Bounded_Arithmetic.
- Decision_problem wikiPageID "8336".
- Decision_problem wikiPageRevisionID "589719327".
- Decision_problem hasPhotoCollection Decision_problem.
- Decision_problem subject Category:Computability_theory.
- Decision_problem subject Category:Computational_problems.
- Decision_problem type Abstraction100002137.
- Decision_problem type Attribute100024264.
- Decision_problem type ComputationalProblems.
- Decision_problem type Condition113920835.
- Decision_problem type Difficulty114408086.
- Decision_problem type Problem114410605.
- Decision_problem type State100024720.
- Decision_problem comment "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. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem.".
- Decision_problem label "Beslissingsprobleem".
- Decision_problem label "Decision problem".
- Decision_problem label "Problem decyzyjny (teoria obliczeń)".
- Decision_problem label "Problema de decisión".
- Decision_problem label "Problema de decisão".
- Decision_problem label "Problema decisionale".
- Decision_problem label "Problème de décision".
- Decision_problem label "Проблема разрешимости".
- Decision_problem label "決定問題".
- Decision_problem label "決定性問題".
- Decision_problem sameAs Problema_de_decisión.
- Decision_problem sameAs Problème_de_décision.
- Decision_problem sameAs Problema_decisionale.
- Decision_problem sameAs 決定問題.
- Decision_problem sameAs 결정_문제.
- Decision_problem sameAs Beslissingsprobleem.
- Decision_problem sameAs Problem_decyzyjny_(teoria_obliczeń).
- Decision_problem sameAs Problema_de_decisão.
- Decision_problem sameAs m.029yr.
- Decision_problem sameAs Q3262192.
- Decision_problem sameAs Q3262192.
- Decision_problem sameAs Decision_problem.
- Decision_problem wasDerivedFrom Decision_problem?oldid=589719327.
- Decision_problem depiction Decision_Problem.svg.
- Decision_problem isPrimaryTopicOf Decision_problem.
