patternMinor
Hardness of finding a true or a false assignment into a generic boolean formula?
Viewed 0 times
genericbooleanhardnessintotruefalseassignmentfindingformula
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#7193, answer score: 2
Revisions (0)
No revisions yet.