SAT Distributions with Phase Transitions between Decision and Optimization Problems

DOI10.1016/S1571-0653(04)00459-7MaRDI QIDQ3439111zbMATH OpenOpenAlexFDO

Authors Tassos Dimitriou

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1571-0653(04)00459-7

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• SAT distributions with planted assignments and phase transitions between decision and optimization problems
• A wealth of SAT distributions with planted assignments
• An Empirical Study of MAX-2-SAT Phase Transitions
• scientific article; zbMATH DE number 2079360
• scientific article; zbMATH DE number 2084703

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A study of complexity transitions on the asymmetric traveling salesman problem
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Determining computational complexity from characteristic ``phase transitions
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 2084703 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• Phase transitions and the search problem
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The TSP phase transition

Cited in

(3)

• SAT distributions with planted assignments and phase transitions between decision and optimization problems
• Generating weighted MAX-2-SAT instances with frustrated loops: an RBM case study
• A wealth of SAT distributions with planted assignments

Describes a project that uses

Uses Software

• Walksat

This page was built for publication: SAT Distributions with Phase Transitions between Decision and Optimization Problems

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