Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Function_problem> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- Function_problem abstract "In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO. Notable examples include the travelling salesman problem, which asks for the route taken by the salesman, and the integer factorization problem, which asks for the list of factors. Function problems are more awkward to study than decision problems because they don't have an obvious analogue in terms of languages, and because the notion of reduction between problems is more subtle as you have to transform the output as well as the input. Function problems can be sorted into complexity classes in the same way as decision problems. For example FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time, and FNP is the set of function problems which can be solved by a non-deterministic Turing machine in polynomial time.For all function problems in which the solution is polynomially bounded, there is an analogous decision problem such that the function problem can be solved by polynomial-time Turing reduction to that decision problem. For example, the decision problem analogue to the travelling salesman problem is this:Given a weighted directed graph and an integer K, is there a Hamiltonian path (or Hamiltonian cycle if the salesman must return home) with total weight less than or equal to K?Given a solution to this problem, we can solve the travelling salesman problem as follows. Let be the number of edges and be the weight of edge . First rescale and perturb the weights of the edges by assigning to edge the new weight . This doesn't change the shortest Hamiltonian path, but makes sure that it is unique. Now add the weights of all edges to get a total weight . Find the weight of the shortest Hamiltonian path by binary search: is there a Hamiltonian path with weight is there a path with weight etc. Then having found the weight of the shortest Hamilton path, determine which edges are in the path by asking for each edge whether there is a Hamiltonian path with weight for the graph modified so that edge has weight (if there is no such path in the modified graph, then edge must be in the shortest path for the original graph). This places the travelling salesman problem in the complexity class FPNP (the class of function problems which can be solved in polynomial time on a deterministic Turing machine with an oracle for a problem in NP), and in fact it is complete for that class.".
- Function_problem wikiPageID "663345".
- Function_problem wikiPageRevisionID "541185939".
- Function_problem hasPhotoCollection Function_problem.
- Function_problem subject Category:Computational_problems.
- Function_problem type Abstraction100002137.
- Function_problem type Attribute100024264.
- Function_problem type ComputationalProblems.
- Function_problem type Condition113920835.
- Function_problem type Difficulty114408086.
- Function_problem type Problem114410605.
- Function_problem type State100024720.
- Function_problem comment "In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO. Notable examples include the travelling salesman problem, which asks for the route taken by the salesman, and the integer factorization problem, which asks for the list of factors.".
- Function_problem label "Function problem".
- Function_problem label "Problema de função".
- Function_problem label "Problema di funzione".
- Function_problem label "功能性問題".
- Function_problem label "関数問題".
- Function_problem sameAs Problema_di_funzione.
- Function_problem sameAs 関数問題.
- Function_problem sameAs 함수_문제.
- Function_problem sameAs Problema_de_função.
- Function_problem sameAs m.030vhs.
- Function_problem sameAs Q906766.
- Function_problem sameAs Q906766.
- Function_problem sameAs Function_problem.
- Function_problem wasDerivedFrom Function_problem?oldid=541185939.
- Function_problem isPrimaryTopicOf Function_problem.