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.

  • 2
    $\begingroup$ I'm a bit confused. If the question was answered in several papers, why ask here for an answer? $\endgroup$ Jul 30, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 18:00


Browse other questions tagged or ask your own question.