Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to ♯P-complete.
Nothing was collected or created yet.
♯P-complete
View on Wikipediafrom Wikipedia
The #P-complete problems (pronounced "sharp P complete", "number P complete", or "hash 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 time. In some cases parsimonious reductions, a more specific type of reduction that preserves the exact number of solutions, are used.
#P-complete problems are at least as hard as NP-complete problems.[1] A polynomial-time algorithm for solving a #P-complete problem, if it existed, would solve the P versus NP problem by implying that P and NP are equal. No such algorithm is known, nor is a proof known that such an algorithm does not exist.
Examples
[edit]Examples of #P-complete problems include:
- How many different variable assignments will satisfy a given general Boolean formula? (#SAT)
- How many different variable assignments will satisfy a given DNF formula?
- How many different variable assignments will satisfy a given 2-satisfiability problem?
- How many perfect matchings are there for a given bipartite graph?
- What is the value of the permanent of a given matrix whose entries are 0 or 1? (See #P-completeness of 01-permanent.)
- How many graph colorings using k colors are there for a particular graph G?
- How many different linear extensions are there for a given partially ordered set, or, equivalently, how many different topological orderings are there for a given directed acyclic graph?[2]
These are all necessarily members of the class #P as well. As a non-example, consider the case of counting solutions to a 1-satisfiability problem: a series of variables that are each individually constrained, but have no relationships with each other. The solutions can be efficiently counted, by multiplying the number of options for each variable in isolation. Thus, this problem is in #P, but cannot be #P-complete unless #P=FP. This would be surprising, as it would imply that P=NP=PH.
Easy problems with hard counting versions
[edit]Some #P-complete problems correspond to easy (polynomial time) problems. Determining the satisfiability of a Boolean formula in disjunctive normal form is easy: such a formula is satisfiable if and only if it contains a satisfiable conjunction (one that does not contain a variable and its negation), whereas counting the number of satisfying assignments is #P-complete. Furthermore, deciding 2-satisfiability is easy compared to counting the number of satisfying assignments. Topologically sorting is easy in contrast to counting the number of topological sortings. A single perfect matching can be found in polynomial time, but counting all perfect matchings is #P-complete. The perfect matching counting problem was the first counting problem corresponding to an easy P problem shown to be #P-complete, in a 1979 paper by Leslie Valiant which also defined the class #P and the #P-complete problems for the first time.[3]
Approximation
[edit]There are probabilistic algorithms that return good approximations to some #P-complete problems with high probability. This is one of the demonstrations of the power of probabilistic algorithms.
Many #P-complete problems have a fully polynomial-time randomized approximation scheme, or "FPRAS," which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required. Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.[4]
References
[edit]- ^ Valiant, Leslie G. (August 1979). "The Complexity of Enumeration and Reliability Problems" (PDF). SIAM Journal on Computing. 8 (3): 410–421. doi:10.1137/0208032.
- ^ Brightwell, Graham R.; Winkler, Peter (1991). "Counting linear extensions". Order. 8 (3): 225–242. doi:10.1007/BF00383444. S2CID 119697949..
- ^ Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science. 8 (2). Elsevier: 189–201. doi:10.1016/0304-3975(79)90044-6.
- ^ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science. 43. Elsevier: 169–188. doi:10.1016/0304-3975(86)90174-x.
Further reading
[edit]- Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8.
♯P-complete
View on Grokipediafrom Grokipedia
♯P-complete problems are the hardest counting problems in the complexity class ♯P, meaning they are in ♯P and every function in ♯P is polynomial-time Turing reducible to them.[1] Introduced by Leslie Valiant in 1979, ♯P-completeness captures the intractability of counting the number of solutions to decision problems in NP, distinguishing it from decision-based complexity classes like NP-complete.[2]
The class ♯P consists of all functions f: {0,1}* → ℕ that count the number of accepting paths of a nondeterministic polynomial-time Turing machine.[1] Formally, f is in ♯P if there exists a polynomial p and a polynomial-time verifier M such that for every input x, f(x) equals the number of witnesses y of length p(|x|) for which M(x,y) accepts.[1] This class naturally extends NP by shifting focus from existence to enumeration, and it includes functions like the number of satisfying assignments to a Boolean formula (#SAT).[1]
A function f in ♯P is ♯P-complete if every g in ♯P belongs to FP^(f), the class of functions computable in polynomial time with oracle access to f.[1] Completeness is typically established using Turing reductions, though parsimonious reductions—bijections that preserve the exact number of solutions—are used for certain proofs to maintain counting precision.[1] Valiant's framework also employed algebraic projections for completeness over fields, linking combinatorial counting to polynomial computations.[2]
Prominent examples of ♯P-complete problems include computing the permanent of a 0-1 matrix, which sums over all perfect matchings in a bipartite graph and was proven complete by Valiant.[2] Other canonical instances are #SAT (counting satisfying truth assignments), counting Hamiltonian cycles in a graph, and counting the number of satisfying assignments to a monotone 2-DNF formula.[1] These problems highlight how even slight modifications to NP-complete decision tasks—such as asking "how many?" instead of "is there at least one?"—can lead to dramatically increased hardness.
♯P-completeness has profound implications for computational complexity, as solving any ♯P-complete problem in polynomial time would imply P = NP, since decision versions can be derived from counting via binary search or parity checks.[3] It also connects to broader hierarchies: Toda's theorem shows that the entire polynomial hierarchy PH is contained in P^♯P (polynomial time with one ♯P oracle query), underscoring the power of counting oracles.[1] Despite extensive study, no polynomial-time algorithms exist for ♯P-complete problems, and approximation remains challenging, with results like inapproximability under certain assumptions.[3]
holds exactly for all inputs x, without any scaling factor or approximation. This contrasts with weaker counting reductions that might multiply the solution count by a polynomial factor. Such exact preservation makes parsimonious reductions a cornerstone for establishing ♯P-completeness in a direct manner, as they inherit the hardness properties without additional computational overhead for adjusting counts.[6] Parsimonious reductions offer significant advantages over other reduction types used in ♯P-completeness proofs. They are stronger than Turing reductions (which allow oracle queries and may approximate or combine counts) because the exact bijection implies immediate hardness transfer for both exact counting and the underlying decision problem—if f(x) > 0, then g(R(x)) > 0 via a many-one reduction on the decision versions. This dual hardness is particularly valuable for self-reducible problems like #SAT, where the structure enables iterative construction of instances while maintaining solution counts, facilitating proofs of completeness under parsimonious reductions from general ♯P problems.[5][7] Despite their strength, parsimonious reductions have limitations: not all ♯P-complete problems admit them between each other. For instance, while both #SAT and the permanent are ♯P-complete, the reduction from #SAT to the permanent relies on more general counting reductions rather than parsimonious ones.[5]
Fundamentals
Definition of ♯P
♯P is a complexity class that captures the computational difficulty of counting problems, serving as the functional analogue to the decision class NP. Introduced by Leslie G. Valiant in 1979 to formalize the hardness of problems like computing the permanent of a matrix, ♯P consists of functions that count solutions verifiable in polynomial time.[4][3] Formally, a function belongs to ♯P if there exists a polynomial and a nondeterministic Turing machine that runs in time such that, for every input , equals the number of accepting computation paths of on . Equivalently, is in ♯P if there is a polynomial-time deterministic verifier and a polynomial such that [3][1] This definition ensures that ♯P functions are total, meaning they are defined and computable for every input string .[3] The class ♯P relates closely to NP, as every decision problem in NP corresponds to a natural counting problem in ♯P: whereas NP verifies the existence of at least one accepting path (i.e., ), ♯P requires computing the exact number of such paths. Functions in ♯P are polynomially bounded, satisfying for some polynomial , reflecting the exponential growth in the number of possible nondeterministic choices within polynomial time.[3][1]♯P-Completeness Criteria
A function problem in is -complete if it is -hard, meaning that every function is polynomial-time Turing reducible to .[1] This Turing reduction allows a polynomial-time algorithm for that makes polynomially many oracle queries to .[1] A stronger condition for -completeness uses parsimonious reductions, which map instances such that the number of solutions is exactly preserved, implying the Turing reduction while directly equating solution counts.[5] Unlike -completeness, where hardness concerns decision problems, -completeness captures the difficulty of exact counting across all problems, which inherently subsumes because the existence of witnesses (as in ) can be extracted from solution counts via techniques like self-reducibility.[1] For instance, deciding satisfiability reduces to checking if the count of satisfying assignments exceeds zero.[1] If a -complete problem could be solved in polynomial time, it would imply , collapsing these classes since polynomial-time solvability for a complete problem enables efficient solutions for all functions, including those encoding decisions.[1] No such polynomial-time algorithm is known, underscoring the presumed intractability of -complete problems.[1] The first problem proven -complete was computing the permanent of a - matrix, established by Valiant in 1979 through reductions showing its hardness for the class.90044-6)Reductions for Counting Problems
Parsimonious Reductions
A parsimonious reduction provides a particularly strong form of transformation between counting problems in the complexity class ♯P. Specifically, a parsimonious reduction from a counting function f to a counting function g is a polynomial-time computable function R that maps instances x of f to instances R(x) of g such that the number of accepting solutions for f(x) exactly equals the number for g(R(x)). This preservation occurs through a polynomial-time computable bijection between the solution sets of x and R(x), ensuring no inflation or deflation of solution counts.[6] Formally, if R is the reduction, thenholds exactly for all inputs x, without any scaling factor or approximation. This contrasts with weaker counting reductions that might multiply the solution count by a polynomial factor. Such exact preservation makes parsimonious reductions a cornerstone for establishing ♯P-completeness in a direct manner, as they inherit the hardness properties without additional computational overhead for adjusting counts.[6] Parsimonious reductions offer significant advantages over other reduction types used in ♯P-completeness proofs. They are stronger than Turing reductions (which allow oracle queries and may approximate or combine counts) because the exact bijection implies immediate hardness transfer for both exact counting and the underlying decision problem—if f(x) > 0, then g(R(x)) > 0 via a many-one reduction on the decision versions. This dual hardness is particularly valuable for self-reducible problems like #SAT, where the structure enables iterative construction of instances while maintaining solution counts, facilitating proofs of completeness under parsimonious reductions from general ♯P problems.[5][7] Despite their strength, parsimonious reductions have limitations: not all ♯P-complete problems admit them between each other. For instance, while both #SAT and the permanent are ♯P-complete, the reduction from #SAT to the permanent relies on more general counting reductions rather than parsimonious ones.[5]