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....
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ 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? $\endgroup$– user834Aug 18, 2011 at 6:52
-
$\begingroup$ Please also specify if you are trying to compute the exact value or are allowing for approximate values. $\endgroup$– Tyson WilliamsAug 18, 2011 at 13:21
-
1$\begingroup$ "the problem goes from being easy to hard and back to hard again" You mean "easy to hard and back to easy again"? $\endgroup$– Tyson WilliamsAug 19, 2011 at 2:20
-
1$\begingroup$ 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. $\endgroup$– user834Aug 19, 2011 at 17:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 19, 2011 at 18:54