|
Mučnik Reducibility
In computability theory, a set P of functions \mathbb \rarr \mathbb is said to be Mučnik-reducible to another set Q of functions \mathbb \rarr \mathbb when for every function g in Q, there exists a function f in P which is Turing-reducible to g. Unlike most reducibility relations in computability, Mučnik reducibility is not defined between functions \mathbb \rarr \mathbb but between sets of such functions. These sets are called "mass problems" and can be viewed as problems with more than one solution. Informally, P is Mučnik-reducible to Q when any solution of Q can be used to compute some solution of P. See also * Medvedev reducibility * Turing reducibility In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm ... * Reduction (computability) References ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computability Theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definable set, definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: * What does it mean for a function (mathematics), function on the natural numbers to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of computational complexity theory ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing-reducible
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm that could be used to solve A if it had access to a subroutine for solving B. The concept can be analogously applied to function problems. If a Turing reduction from A to B exists, then every algorithm for B can be used to produce an algorithm for A, by inserting the algorithm for B at each place where the oracle machine computing A queries the oracle for B. However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for B or the oracle machine computing A. A Turing reduction in which the oracle machine runs in polynomial time is known as a Cook reduction. The first formal definition of relative computability, then called relative r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reduction (computability Theory)
In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively convert a method for deciding membership in B into a method for deciding membership in A? If the answer to this question is affirmative then A is said to be reducible to B. The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set A then A must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable. Reducibility relations A reducibility relation is a binary relation on sets of natural numbers that is * Reflexive: Every set is reducible to itself. * Transitive: If a set A is reducible to a set B and B is reducible to a set C then A is reducible to C. These two properties imply that reducib ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Medvedev Reducibility
In computability theory, a set ''P'' of functions \mathbb \rarr \mathbb is said to be Medvedev-reducible to another set ''Q'' of functions \mathbb \rarr \mathbb when there exists an oracle Turing machine which computes some function of ''P'' whenever it is given some function from ''Q'' as an oracle. Medvedev reducibility is a uniform variant of Mučnik reducibility, requiring a single oracle machine that can compute some function of ''P'' given any oracle from ''Q'', instead of a family of oracle machines, one per oracle from ''Q'', which compute functions from ''P''. See also * Mučnik reducibility * Turing reducibility In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm ... * Reduction (computability) References Theoretical computer science Reduction ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing Reducibility
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm that could be used to solve A if it had access to a subroutine for solving B. The concept can be analogously applied to function problems. If a Turing reduction from A to B exists, then every algorithm for B can be used to produce an algorithm for A, by inserting the algorithm for B at each place where the oracle machine computing A queries the oracle for B. However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for B or the oracle machine computing A. A Turing reduction in which the oracle machine runs in polynomial time is known as a Cook reduction. The first formal definition of relative computability, then called relative ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reduction (computability)
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first. Intuitively, problem ''A'' is reducible to problem ''B'', if an algorithm for solving problem ''B'' efficiently (if it exists) could also be used as a subroutine to solve problem ''A'' efficiently. When this is true, solving ''A'' cannot be harder than solving ''B''. "Harder" means having a higher estimate of the required computational resources in a given context (e.g., higher time complexity, greater memory requirement, expensive need for extra hardware processor cores for a parallel solution compared to a single-threaded solution, etc.). The existence of a reduction from ''A'' to ''B'' can be written in the shorthand notation ''A'' ≤m ''B'', usually with a subscript on the ≤ to indicate the typ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
