Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

2 Answers 2

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
1  
@SAT No, unfortunately not. An exponential blowup of the formula is possible in some cases. –  Juho Dec 5 '12 at 20:29
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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