A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES

DOI10.1142/S0129054113500251zbMath1290.68051MaRDI QIDQ5401563

Guangyan Zhou, Zong Sheng Gao

Publication date: 10 March 2014

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

upper bound\((2 + p)\)-SATdouble flips

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT

Cites Work

• A threshold for unsatisfiability
• Replica bounds for optimization problems and diluted spin systems
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• On the satisfiability threshold of formulas with three literals per clause
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• New versions of Suen's correlation inequality
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Rigorous results for random (\(2+p)\)-SAT