# Hardness of finding a true or a false assignment into a generic boolean formula?

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?

• 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". – Yuval Filmus Dec 5 '12 at 19:52
• 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. – SAT Dec 5 '12 at 20:17
• @SAT, random formula of some kind is not a definition. The result is about a very particular and natural distribution of formulas. – Kaveh Jan 23 '13 at 5:30

## 2 Answers

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

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.

• but if i have a generic formula the operation of converting to SAT is polinomial in space and time? – SAT Dec 5 '12 at 19:37
• @SAT No, unfortunately not. An exponential blowup of the formula is possible in some cases. – Juho Dec 5 '12 at 20:29
• 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. – Kaveh Jan 23 '13 at 5:20