3
$\begingroup$

I read some research that analyzes the hardness of SAT solving in the average case. In fact, for a 3CNF formula if you compute the ratio of clause to variables there is an interval (more or less between 4 and 5) in which solving the formula is hard. But it is easy (between 0 and 4) high probability of satisfiable assignment and high probability of unsatisfiable assignment after ratio 5.

My question is, what about a generic formula that is not in normal form. We can say something about its hardness?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What is a generic formula? Do you mean a random formula of some kind, or an arbitrary formula? SAT is believed to be worst-case hard, but for average-case hardness, you will need to explain what you mean by "average case". $\endgroup$
    – Yuval Filmus
    Commented Dec 5, 2012 at 19:52
  • $\begingroup$ sure, with generic formula i mean a random formula of some kind. With average case hardness i say that the formula is hard on the average. taking a random formula it is with high probability hard to solve or easy to solve. $\endgroup$
    – SAT
    Commented Dec 5, 2012 at 20:17
  • $\begingroup$ @SAT, random formula of some kind is not a definition. The result is about a very particular and natural distribution of formulas. $\endgroup$
    – Kaveh
    Commented Jan 23, 2013 at 5:30

2 Answers 2

Reset to default
2
$\begingroup$

You can always convert your formula or circuit to an equivalent CNF formula of polynomial size.

The result you mention is only for 3CNF formulas. In general for kCNF-SAT the assumed threshold phenomenon happens on a point depending on $k$, the values you mention are only for 3CNF-SAT.

Also remember what these result say is w.h.p. in a particular distribution of k-CNF formulas. It doesn't mean that this will hold for all formulas. In fact it is quite easy to come up with formulas that have values mentioned in the range but are easy and also formulas that are outside this range but are hard (think about padding formulas to obtain your desired ration). So given a particular 3CNF formula with some clause ration, you can't say anything about its difficulty (or the time it will take a particular SAT solver to solve it).

Improve this answer
$\endgroup$
1
$\begingroup$

If your question really is about hardness of finding either a true or false assignment to an arbitrary formula, this is always easy. Pick any assignment and it will always either satisfy the formula or not.

It is only the random instances of SAT that exhibit the phase transition you mention. There is also work that tries to characterize the hardness of an arbitrary formula. For more on this, see my answer to the question Measuring the difficulty of SAT instances. Also, recall that every propositional formula can be converted into an equivalent formula that is in CNF. See Conversion into CNF on Wikipedia for example.

Improve this answer
$\endgroup$
3
  • $\begingroup$ but if i have a generic formula the operation of converting to SAT is polinomial in space and time? $\endgroup$
    – SAT
    Commented Dec 5, 2012 at 19:37
  • 1
    $\begingroup$ @SAT No, unfortunately not. An exponential blowup of the formula is possible in some cases. $\endgroup$
    – Juho
    Commented Dec 5, 2012 at 20:29
  • 1
    $\begingroup$ We can always introduce new propositional variables to obtain an equivalent polysize CNF formula as is done in reduction from SAT to CNF-SAT, the blow up is only if we don't introduce new variables. $\endgroup$
    – Kaveh
    Commented Jan 23, 2013 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.