<p>For counting independent sets, there is a recent proof for a computational phase transition, by Allan Sly:
<a href="http://arxiv.org/abs/1005.5584">http://arxiv.org/abs/1005.5584</a>
(the algorithm is by Dror Weitz from 2006; Allan proved the matching hardness and co-won the best paper award in FOCS'10 for that)</p>

<p>Note that for random 3SAT and similar problems there is no proof that those problems are indeed hard in the appropriate interval. When you go to the harder counting problems, it becomes easier to prove the hardness.</p>

CC BY-SA 3.0
2011-08-19T18:54:32.157Z
2011-08-19T19:14:29.317Z
2011-08-19T19:14:29.317Z
Dana Moshkovitz
<p>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?<br> <br>Update:<br>
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? <br><br>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....  </p>

CC BY-SA 3.0
2011-08-18T06:52:27.933Z
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?
user834
CC BY-SA 3.0
2011-08-18T13:21:46.010Z
Please also specify if you are trying to compute the exact value or are allowing for approximate values.
Tyson Williams
CC BY-SA 3.0
2011-08-19T02:20:36.467Z
"the problem goes from being easy to hard and back to hard again"

You mean "easy to hard and back to easy again"?
Tyson Williams
CC BY-SA 3.0
2011-08-19T17:22:46.357Z
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.
user834
<cc.complexity-theory><counting-complexity><phase-transition>
What do we know about the phase transition of #P-Complete problems?
Tayfun Pay
# What do we know about the phase transition of #P-Complete problems?

(Asked by: username_0 on 2011-08-18)

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....

**Tags:** cc.complexity-theory, counting-complexity, phase-transition
> **Comments:**
> **username_1**: 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?  
> **username_2**: Please also specify if you are trying to compute the exact value or are allowing for approximate values.  
> **username_2**: "the problem goes from being easy to hard and back to hard again"  You mean "easy to hard and back to easy again"?  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-08-19. Score: 7 | Accepted answer

For counting independent sets, there is a recent proof for a computational phase transition, by Allan Sly:
<http://arxiv.org/abs/1005.5584>
(the algorithm is by Dror Weitz from 2006; Allan proved the matching hardness and co-won the best paper award in FOCS'10 for that)

Note that for random 3SAT and similar problems there is no proof that those problems are indeed hard in the appropriate interval. When you go to the harder counting problems, it becomes easier to prove the hardness.


---

