Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Search_problem> ?p ?o. }
Showing items 1 to 26 of
26
with 100 items per page.
- Search_problem abstract "In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if: If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them) If x is such that there is no y such that R(x, y) then T rejects xIntuitively, the problem consists in finding structure "y" in object "x". An algorithm is said to solve the problem if at least one corresponding structure exists, and then one occurrence of this structure is outputted; otherwise, the algorithm stops with an appropriate output ("Item not found" or any message of the like).Such problems occur very frequently in graph theory, for example, where searching graphs for structures such as particular matching, cliques, independent set, etc. are subjects of interest.Note that the graph of a partial function is a binary relation, and if T calculates a partial function then there is at most one possible output.A relation R can be viewed as a search problem, and a Turing machine which calculates R is also said to solve it. Every search problem has a corresponding decision problem, namelyThis definition may be generalized to n-ary relations using any suitable encoding which allows multiple strings to be compressed into one string (for instance by listing them consecutively with a delimiter).".
- Search_problem wikiPageID "1471816".
- Search_problem wikiPageRevisionID "585808672".
- Search_problem hasPhotoCollection Search_problem.
- Search_problem id "3425".
- Search_problem title "search problem".
- Search_problem subject Category:Computational_problems.
- Search_problem type Abstraction100002137.
- Search_problem type Attribute100024264.
- Search_problem type ComputationalProblems.
- Search_problem type Condition113920835.
- Search_problem type Difficulty114408086.
- Search_problem type Problem114410605.
- Search_problem type State100024720.
- Search_problem comment "In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation.".
- Search_problem label "Problema de busca".
- Search_problem label "Search problem".
- Search_problem label "Suchproblem".
- Search_problem sameAs Suchproblem.
- Search_problem sameAs Problema_de_busca.
- Search_problem sameAs m.0545mf.
- Search_problem sameAs Q2362762.
- Search_problem sameAs Q2362762.
- Search_problem sameAs Search_problem.
- Search_problem wasDerivedFrom Search_problem?oldid=585808672.
- Search_problem isPrimaryTopicOf Search_problem.