Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPhase Transition in Unrestricted Random SAT
149
0
0.0
(
0
)
Added by
Bernd Schuh
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Bernd R. Schuh
Ask ChatGPT about the research
No Arabic abstract
For random CNF formulae with m clauses, n variables and an unrestricted number of literals per clause the transition from high to low satisfiability can be determined exactly for large n. The critical density m/n turns out to be strongly n-dependent, ccr = ln(2)/(1-p)^^n, where pn is the mean number of positive literals per clause.This is in contrast to restricted random SAT problems (random K-SAT), where the critical ratio m/n is a constant. All transition lines are calculated by the second moment method applied to the number of solutions N of a formula. In contrast to random K-SAT, the method does not fail for the unrestricted model, because long range interactions between solutions are not cut off by disorder.
rate research
Read More
A heuristic model procedure for determining satisfiability of CNF-formulae is set up and described by nonlinear recursion relations for m (number of clauses), n (number of variables) and clause filling k. The system mimicked by the recursion undergoes a sharp transition from bounded running times (easy) to uncontrolled runaway behaviour (hard). Thus the parameter space turns out to be separated into regions with qualitatively different efficiency of the model procedure. The transition results from a competition of exponential blow up by branching versus growing number of orthogonal clauses.
The aim of this short note is mainly pedagogical. It summarizes some knowledge about Boolean satisfiability (SAT) and the P=NP? problem in an elementary mathematical language. A convenient scheme to visualize and manipulate CNF formulae is introduced. Also some results like the formulae for the number of unsatisfied clauses and the number of solutions might be unknown.
Limits on the number of satisfying assignments for CNS instances with n variables and m clauses are derived from various inequalities. Some bounds can be calculated in polynomial time, sharper bounds demand information about the distribution of the number of unsatisfied clauses. Quite generally, the number of satisfying assignments involve variance and mean of this distribution. For large formulae, m>>1, bounds vary with 2**n/n, so they may be of use only for instances with a large number of satisfying assignments.
We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Schoning, Schuler, and Watanabe in [STACS02]. Thereby, we obtain an O(1.3303^n)-time deterministic algorithm for 3-SAT, which is currently fastest.
MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size $k$, for some $kge 2$. We refer to this problem as MAX NAE-${k}$-SAT. For $k=2$, it is essentially the celebrated MAX CUT problem. For $k=3$, it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For $kge 4$, it is known that an approximation ratio of $1-frac{1}{2^{k-1}}$, obtained by choosing a random assignment, is optimal, assuming $P e NP$. For every $kge 2$, an approximation ratio of at least $frac{7}{8}$ can be obtained for MAX NAE-${k}$-SAT. There was some hope, therefore, that there is also a $frac{7}{8}$-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no $frac{7}{8}$-approximation algorithm for MAX NAE-SAT, assuming the unique games conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-${3,5}$-SAT (i.e., MAX NAE-SAT where all clauses have size $3$ or $5$), the best approximation ratio that can be achieved, assuming UGC, is at most $frac{3(sqrt{21}-4)}{2}approx 0.8739$. Using calculus of variations, we extend the analysis of ODonnell and Wu for MAX CUT to MAX NAE-${3}$-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-${3}$-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is $approx 0.9089$. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-${3,5}$-SAT with a conjectured approximation ratio of 0.8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0.8698.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
