Super solutions of random \((3 + p)\)-SAT

DOI10.1016/j.tcs.2019.04.015zbMath1430.68167OpenAlexW2944997627MaRDI QIDQ2326395

Bin Wang, Guangyan Zhou

Publication date: 7 October 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.04.015

zbMATH Keywords

phase transitionunit clause\((1, 0)\)-satisfiablesuper solution

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
• A threshold for unsatisfiability
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Differential equations for random processes and random graphs
• On the satisfiability threshold of formulas with three literals per clause
• The unsatisfiability threshold revisited
• Proof of the Satisfiability Conjecture for Large k
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• The probabilistic analysis of a greedy satisfiability algorithm
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Rigorous results for random (\(2+p)\)-SAT
• Lower bounds for random 3-SAT via differential equations