# What do we know about the phase transition of #P-Complete problems?

What is known about the phase transition in #P-Complete problems? Specifically, does there exists a different phase transition for #DNF-k-SAT and #CNF-k-SAT?

Update:
As we know, there is a phase transition in Random k-SAT where solving the problem goes from being easy to hard and back to easy again. I would like to know if there is such a phenomenon for #P-Complete problems as well. More importantly, if there exists a phase transition, is it same for #CNF-k-SAT and #DNF-k-SAT?

I am thinking that there is some type of phase transition for #CNF-k-SAT. On the other hand, I do not think there is phase transition for #DNF-k-SAT and the problem gets harder as we add more clauses....

• Could you clarify a bit what you mean by "the" #P phase transition? The phase transition for NP-Complete problems is usually taken to be the probability of a random instance drawn from some parameterized distribution being satisfiable (for 3-SAT, say). What is the transition for #P? When a certain percentage are satisfiable? Aug 18 '11 at 6:52
• Please also specify if you are trying to compute the exact value or are allowing for approximate values. Aug 18 '11 at 13:21
• "the problem goes from being easy to hard and back to hard again" You mean "easy to hard and back to easy again"? Aug 19 '11 at 2:20
• I'm still unclear as to what quantity it is that you are measuring. The 3-SAT phase transition (as an example for concreteness) is taken to be the probability of a solution existing. i.e. Of at least one solution existing. So if "the" #P transition is taken to mean the probability of a non zero count of solutions, then those two are equivalent. Also, there is a difference between "easy" and "a solution existing" as the former implies a polynomial algorithm whereas the latter does not. NPP is notorious for being difficult nearly everywhere, even far away from the transition point. Aug 19 '11 at 17:22