A tighter upper bound for random MAX \(2\)-SAT

DOI10.1016/j.ipl.2010.11.002zbMath1260.68164MaRDI QIDQ1944049

Xuelin Xu, Zong Sheng Gao, Ke Xu

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.11.002

zbMATH Keywords

computational complexity; upper bound; first-moment argument; MAX \(2\)-SAT

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Phase Transition for Maximum Not-All-Equal Satisfiability, An upper (lower) bound for Max (Min) CSP, NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY, Lower and Upper Bounds for Random Mimimum Satisfiability Problem

Uses Software

• MAX-2-SAT

Cites Work

• Some simplified NP-complete graph problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• New worst-case upper bounds for SAT
• The scaling window of the 2-SAT transition
• An Empirical Study of MAX-2-SAT Phase Transitions
• New Upper Bounds for Maximum Satisfiability
• Random MAX SAT, random MAX CUT, and their phase transitions
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Some optimal inapproximability results
• Unnamed Item
• Unnamed Item
• Unnamed Item