Phase Transition for Maximum Not-All-Equal Satisfiability

DOI10.1007/978-3-319-59605-1_24zbMath1489.68177OpenAlexW2618442377MaRDI QIDQ4632221

Tingting Zou, Junping Zhou, Shuli Hu, Minghao Yin

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-59605-1_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general model and thresholds for random constraint satisfaction problems
• An upper (lower) bound for Max (Min) CSP
• The TSP phase transition
• The SAT phase transition
• A tighter upper bound for random MAX \(2\)-SAT
• The number of solutions for random regular NAE-SAT
• A logical approach to efficient Max-SAT solving
• PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Random MAX SAT, random MAX CUT, and their phase transitions
• Satisfiability threshold for random regular NAE-SAT
• Determining computational complexity from characteristic ‘phase transitions’
• Catching the k-NAESAT threshold