Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Decision_problem> ?p ?o }
- 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. 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.".
- Decision_problem thumbnail Decision_Problem.svg?width=300.
- Decision_problem wikiPageID "8336".
- Decision_problem wikiPageLength "8047".
- Decision_problem wikiPageOutDegree "51".
- Decision_problem wikiPageRevisionID "703568077".
- Decision_problem wikiPageWikiLink ALL_(complexity).
- Decision_problem wikiPageWikiLink Algorithm.
- Decision_problem wikiPageWikiLink Alphabet_(formal_languages).
- Decision_problem wikiPageWikiLink Boolean_satisfiability_problem.
- Decision_problem wikiPageWikiLink Category:Computability_theory.
- Decision_problem wikiPageWikiLink Category:Computational_problems.
- Decision_problem wikiPageWikiLink Co-NP-complete.
- Decision_problem wikiPageWikiLink Complement_(complexity).
- Decision_problem wikiPageWikiLink Complete_(complexity).
- Decision_problem wikiPageWikiLink Complexity_class.
- Decision_problem wikiPageWikiLink Computability_theory.
- Decision_problem wikiPageWikiLink Computational_complexity_theory.
- Decision_problem wikiPageWikiLink Computational_problem.
- Decision_problem wikiPageWikiLink Computational_resource.
- Decision_problem wikiPageWikiLink Counting_problem_(complexity).
- Decision_problem wikiPageWikiLink Decidability_(logic).
- Decision_problem wikiPageWikiLink Effective_method.
- Decision_problem wikiPageWikiLink Formal_language.
- Decision_problem wikiPageWikiLink Formal_system.
- Decision_problem wikiPageWikiLink Function_problem.
- Decision_problem wikiPageWikiLink Gödel_numbering.
- Decision_problem wikiPageWikiLink Halting_problem.
- Decision_problem wikiPageWikiLink Hartley_Rogers,_Jr..
- Decision_problem wikiPageWikiLink Indicator_function.
- Decision_problem wikiPageWikiLink List_of_undecidable_problems.
- Decision_problem wikiPageWikiLink Long_division.
- Decision_problem wikiPageWikiLink Many-one_reduction.
- Decision_problem wikiPageWikiLink Michael_Sipser.
- Decision_problem wikiPageWikiLink NP-completeness.
- Decision_problem wikiPageWikiLink NP_(complexity).
- Decision_problem wikiPageWikiLink Optimization_problem.
- Decision_problem wikiPageWikiLink Partial_function.
- Decision_problem wikiPageWikiLink Polynomial-time_reduction.
- Decision_problem wikiPageWikiLink Primality_test.
- Decision_problem wikiPageWikiLink Recursive_set.
- Decision_problem wikiPageWikiLink Recursively_enumerable_set.
- Decision_problem wikiPageWikiLink Search_problem.
- Decision_problem wikiPageWikiLink String_(computer_science).
- Decision_problem wikiPageWikiLink Time_complexity.
- Decision_problem wikiPageWikiLink Turing_degree.
- Decision_problem wikiPageWikiLink Undecidable_problem.
- Decision_problem wikiPageWikiLink Word_problem_(mathematics).
- Decision_problem wikiPageWikiLink Yes–no_question.
- Decision_problem wikiPageWikiLink Zohar_Manna.
- Decision_problem wikiPageWikiLink File:Decision_Problem.svg.
- Decision_problem wikiPageWikiLinkText "Decision Problem".
- Decision_problem wikiPageWikiLinkText "Decision problem".
- Decision_problem wikiPageWikiLinkText "Problems".
- Decision_problem wikiPageWikiLinkText "algorithmic problem of deciding".
- Decision_problem wikiPageWikiLinkText "decidability".
- Decision_problem wikiPageWikiLinkText "decidable".
- Decision_problem wikiPageWikiLinkText "decide".
- Decision_problem wikiPageWikiLinkText "decided".
- Decision_problem wikiPageWikiLinkText "deciding".
- Decision_problem wikiPageWikiLinkText "decision problem".
- Decision_problem wikiPageWikiLinkText "decision problems".
- Decision_problem wikiPageWikiLinkText "decision procedure".
- Decision_problem wikiPageWikiLinkText "decision procedures".
- Decision_problem wikiPageWikiLinkText "decision version".
- Decision_problem wikiPageWikiLinkText "decision".
- Decision_problem wikiPageWikiLinkText "membership problem".
- Decision_problem wikiPageWikiLinkText "partially decidable".
- Decision_problem wikiPageWikiLinkText "problem of determining whether".
- Decision_problem wikiPageWikiLinkText "problem".
- Decision_problem wikiPageWikiLinkText "undecidable".
- Decision_problem wikiPageUsesTemplate Template:About.
- Decision_problem wikiPageUsesTemplate Template:Authority_control.
- Decision_problem wikiPageUsesTemplate Template:Main.
- Decision_problem wikiPageUsesTemplate Template:No_footnotes.
- Decision_problem subject Category:Computability_theory.
- Decision_problem subject Category:Computational_problems.
- Decision_problem hypernym Question.
- Decision_problem type Work.
- Decision_problem type Thing.
- 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.".
- Decision_problem label "Decision problem".
- Decision_problem sameAs Q3262192.
- Decision_problem sameAs সিদ্ধান্ত_সমস্যা.
- Decision_problem sameAs Problema_de_decisió.
- Decision_problem sameAs Rozhodovací_problém.
- Decision_problem sameAs Decidoproblemo.
- Decision_problem sameAs Problema_de_decisión.
- Decision_problem sameAs مسئله_تصمیم.
- Decision_problem sameAs Problème_de_décision.
- Decision_problem sameAs בעיית_הכרעה.
- Decision_problem sameAs Problem_odluke.
- Decision_problem sameAs Լուծելիության_պրոբլեմ.
- Decision_problem sameAs Problema_decisionale.
- Decision_problem sameAs 決定問題.
- Decision_problem sameAs ನಿರ್ಣಯ_ಪ್ರಶ್ನೆ.
- Decision_problem sameAs 결정_문제.
- Decision_problem sameAs Beslissingsprobleem.
- Decision_problem sameAs Problem_decyzyjny_(teoria_obliczeń).
- Decision_problem sameAs Problema_de_decisão.