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

DOI10.1016/j.ipl.2010.11.002zbMath1260.68164OpenAlexW2083324225MaRDI 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 complexityupper boundfirst-moment argumentMAX \(2\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

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

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A tighter upper bound for random MAX \(2\)-SAT