Probabilistic characterization of random Max r-Sat

DOI10.1016/J.DISOPT.2021.100630MaRDI QIDQ2042075zbMATH OpenOpenAlexFDO

Authors Daniel Berend, Yochai Twitto

Publication date 27 July 2021

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2021.100630

zbMATH Keywords

combinatorial optimizationlocal searchfitness landscapesmaximum satisfiabilityautocorrelation lengthprobabilistic characterization

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• Random MAX SAT, random MAX CUT, and their phase transitions
• scientific article; zbMATH DE number 2079360
• Probabilistic performance of a heurisic for the satisfiability problem
• Probabilistic approach to the satisfiability problem

Cites work

• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 6416756 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• A tutorial on the cross-entropy method
• Autocorrelation coefficient for the graph bipartitioning problem
• Autocorrelation measures for the quadratic assignment problem
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Exploiting the deep structure of constraint problems
• Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
• Minimaxsat: an efficient weighted Max-SAT solver
• On a combinatorial game
• On the classification of NP-complete problems in terms of their correlation coefficient
• On the landscape ruggedness of the quadratic assignment problem
• Proof of the satisfiability conjecture for large \(k\)
• SAT-based MaxSAT algorithms
• Sharp thresholds of graph properties, and the $k$-sat problem
• Some optimal inapproximability results
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• The asymptotic \(k\)-SAT threshold
• The first and second Max-SAT evaluations
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Theory and Applications of Satisfiability Testing
• Threshold values of random K‐SAT from the cavity method

Cited in

(2)

• On the Lower Bounds of Random Max 3 and 4-SAT
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$

Describes a project that uses

Uses Software

• CCLS
• MaxHS
• MiniMaxSat
• Walksat
• UBCSAT

This page was built for publication: Probabilistic characterization of random Max \(r\)-Sat

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2042075)