1
$\begingroup$

It was asked here and closed although it is a very specific question witch was exactly answered in several papers. The complexity of 3-SAT problems has a phase transition which reaches the critical point if the ratio of clauses to variables is 4.25.

$\endgroup$
6
  • 2
    $\begingroup$ I'm a bit confused. If the question was answered in several papers, why ask here for an answer? $\endgroup$ – Rick Decker Jul 30 '19 at 18:51
  • $\begingroup$ Random 3-SAT has a phase transition between almost always satisfiable and almost always unsatisfiable instances near a particular clause-to-variables ratio. Instances seem harder to solve near that transition point, but proofs of actual hardness remain elusive. Empirical evidence drawn from running existing algorithms against random instances falls short of an actual proof of hardness. $\endgroup$ – Kyle Jones Jul 31 '19 at 3:26
  • 3
    $\begingroup$ Possible duplicate of How does the number of clauses affect the difficulty of a 3-SAT problem? $\endgroup$ – Juho Jul 31 '19 at 4:43
  • $\begingroup$ I'm voting to close this question as off-topic because it is an attempt to answer a closed question. $\endgroup$ – Discrete lizard Jul 31 '19 at 17:54
  • $\begingroup$ In general, please do not use the question box for answers to other closed questions or discuss the closure of such questions. The place for the second is on Computer Science Meta. That said, I'm not sure if the linked question should have been closed. The answers there seem to indicate that there is something not too broad in there that can be answered. However, I'm not sure, so I'd like to have some input before deciding to reopen it or not. Thoughts? $\endgroup$ – Discrete lizard Jul 31 '19 at 18:00