Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Promise_problem> ?p ?o. }
Showing items 1 to 23 of
23
with 100 items per page.
- Promise_problem abstract "In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes or no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.".
- Promise_problem wikiPageExternalLink download?doi=10.1.1.34.6920&rep=rep1&type=pdf.
- Promise_problem wikiPageExternalLink 018.
- Promise_problem wikiPageID "1471429".
- Promise_problem wikiPageRevisionID "556012845".
- Promise_problem hasPhotoCollection Promise_problem.
- Promise_problem subject Category:Computational_problems.
- Promise_problem type Abstraction100002137.
- Promise_problem type Attribute100024264.
- Promise_problem type ComputationalProblems.
- Promise_problem type Condition113920835.
- Promise_problem type Difficulty114408086.
- Promise_problem type Problem114410605.
- Promise_problem type State100024720.
- Promise_problem comment "In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes or no.".
- Promise_problem label "Promise problem".
- Promise_problem label "承諾問題".
- Promise_problem sameAs m.0544lc.
- Promise_problem sameAs Q130203.
- Promise_problem sameAs Q130203.
- Promise_problem sameAs Promise_problem.
- Promise_problem wasDerivedFrom Promise_problem?oldid=556012845.
- Promise_problem isPrimaryTopicOf Promise_problem.