Phase Transition for Maximum Not-All-Equal Satisfiability

DOI10.1007/978-3-319-59605-1_24MaRDI QIDQ4632221zbMATH OpenOpenAlexFDO

Authors Junping Zhou, Shuli Hu, Tingting Zou, 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)

Recommendations

• Phase transitions of PP-complete satisfiability problems
• An Empirical Study of MAX-2-SAT Phase Transitions
• Locating the phase transition in binary constraint satisfaction problems
• On the phase transitions of (k, q)-SAT
• scientific article; zbMATH DE number 1448978
• Phase transitions of PP-complete satisfiability problems. (Abstract)
• Phase transitions of random constraint satisfaction problems
• An empirical study of phase transitions in binary constraint satisfaction problems
• Phase transitions of EXPSPACE-complete problems

Cites work

• A general model and thresholds for random constraint satisfaction problems
• A logical approach to efficient Max-SAT solving
• A tighter upper bound for random MAX \(2\)-SAT
• An upper (lower) bound for Max (Min) CSP
• Catching the \(k\)-NAESAT threshold
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Determining computational complexity from characteristic ``phase transitions
• scientific article; zbMATH DE number 2084703 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• Phase transitions of EXPSPACE-complete problems: a further step
• Random MAX SAT, random MAX CUT, and their phase transitions
• Satisfiability threshold for random regular NAE-SAT
• The number of solutions for random regular NAE-SAT
• The phase transition in 1-in-k SAT and NAE 3-SAT
• The SAT phase transition
• The TSP phase transition

Cited in

(6)

• The SAT phase transition
• Phase transitions of PP-complete satisfiability problems
• The phase transition in 1-in-k SAT and NAE 3-SAT
• Phase transitions of EXPSPACE-complete problems: a further step
• scientific article; zbMATH DE number 2084703 (Why is no real title available?)
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)

This page was built for publication: Phase Transition for Maximum Not-All-Equal Satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632221)