Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Promise_problem> ?p ?o }
Showing triples 1 to 41 of
41
with 100 triples 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 018.
- Promise_problem wikiPageID "1471429".
- Promise_problem wikiPageLength "3691".
- Promise_problem wikiPageOutDegree "17".
- Promise_problem wikiPageRevisionID "662978153".
- Promise_problem wikiPageWikiLink Category:Computational_problems.
- Promise_problem wikiPageWikiLink Computational_complexity_theory.
- Promise_problem wikiPageWikiLink Computational_problem.
- Promise_problem wikiPageWikiLink Counting_problem_(complexity).
- Promise_problem wikiPageWikiLink Cycle_(graph_theory).
- Promise_problem wikiPageWikiLink Decision_problem.
- Promise_problem wikiPageWikiLink Directed_acyclic_graph.
- Promise_problem wikiPageWikiLink Disjoint_sets.
- Promise_problem wikiPageWikiLink Function_problem.
- Promise_problem wikiPageWikiLink Hamiltonian_path.
- Promise_problem wikiPageWikiLink Information_and_Computation.
- Promise_problem wikiPageWikiLink Lecture_Notes_in_Computer_Science.
- Promise_problem wikiPageWikiLink NP-hardness.
- Promise_problem wikiPageWikiLink Optimization_problem.
- Promise_problem wikiPageWikiLink Path_(graph_theory).
- Promise_problem wikiPageWikiLink Search_problem.
- Promise_problem wikiPageWikiLinkText "Promise-UP".
- Promise_problem wikiPageWikiLinkText "promise problem".
- Promise_problem wikiPageWikiLinkText "promised".
- Promise_problem wikiPageWikiLinkText "restricted".
- Promise_problem wikiPageUsesTemplate Template:Cite_book.
- Promise_problem wikiPageUsesTemplate Template:Cite_conference.
- Promise_problem wikiPageUsesTemplate Template:Cite_journal.
- Promise_problem wikiPageUsesTemplate Template:Citeseerx.
- Promise_problem wikiPageUsesTemplate Template:Reflist.
- Promise_problem subject Category:Computational_problems.
- Promise_problem hypernym Generalization.
- 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 sameAs Q130203.
- Promise_problem sameAs m.0544lc.
- Promise_problem sameAs Q130203.
- Promise_problem sameAs 承諾問題.
- Promise_problem wasDerivedFrom Promise_problem?oldid=662978153.
- Promise_problem isPrimaryTopicOf Promise_problem.