|
♯P-complete
The #P-complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: *The problem is in #P, the class of problems that can be defined as counting the number of accepting paths of a polynomial-time non-deterministic Turing machine. *The problem is #P-hard, meaning that every other problem in #P has a Turing reduction or polynomial-time counting reduction to it. A counting reduction is a pair of polynomial-time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial tim ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time Counting Reduction
In the computational complexity theory of counting problem (complexity), counting problems, a polynomial-time counting reduction is a type of Reduction (complexity), reduction (a transformation from one problem to another) used to define the notion of Complete (complexity), completeness for the complexity class ♯P. These reductions may also be called polynomial many-one counting reductions or weakly parsimonious reductions; they are analogous to many-one reductions for decision problems and they generalize the parsimonious reductions. Definition A polynomial-time counting reduction is usually used to transform instances of a known-hard problem X into instances of another problem Y that is to be proven hard. It consists of two functions f and g, both of which must be computable in polynomial time. The function f transforms inputs for X into inputs for Y, and the function g transforms outputs for Y into outputs for X. These two functions must preserve the correctness of the output. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |