On the Lower Bounds of Random Max 3 and 4-SAT

DOI10.1007/978-3-319-39817-4_26MaRDI QIDQ4632196zbMATH OpenOpenAlexFDO

Authors Guangyan Zhou

Publication date 26 April 2019

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-39817-4_26

zbMATH Keywords

weighting schememaximum satisfiabilitysecond-moment method

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial probability (60C05) Computational aspects of satisfiability (68R07)

Recommendations

• On the lower bounds of random Max 3 and 4-SAT
• A tighter upper bound for random MAX \(2\)-SAT
• Lower bounds for random 3-SAT via differential equations
• scientific article; zbMATH DE number 437557
• Lower and Upper Bounds for Random Mimimum Satisfiability Problem
• Bounding the unsatisfiability threshold of random 3-SAT
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Algorithms and Computation
• Probabilistic characterization of random Max \(r\)-Sat

Cites work

• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• scientific article; zbMATH DE number 3886512 (Why is no real title available?)
• scientific article; zbMATH DE number 2079360 (Why is no real title available?)
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• 1.0957-Approximation Algorithm for Random MAX-3SAT
• A lower bound for the 4-satisfiability threshold
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• On the maximum satisfiability of random formulas
• Some optimal inapproximability results
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

Cited in

(5)

• Lower and Upper Bounds for Random Mimimum Satisfiability Problem
• On the lower bounds of random Max 3 and 4-SAT
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
• Theory and Applications of Models of Computation
• A lower bound for the 4-satisfiability threshold

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: On the Lower Bounds of Random Max 3 and 4-SAT

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