SAT distributions with planted assignments and phase transitions between decision and optimization problems

DOI10.1016/J.DAM.2005.05.006MaRDI QIDQ2581547zbMATH OpenOpenAlexFDO

Authors Tassos Dimitriou

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.006

zbMATH Keywords

assignmentdecision problems

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Discrete location and assignment (90B80)

Recommendations

• SAT Distributions with Phase Transitions between Decision and Optimization Problems
• A wealth of SAT distributions with planted assignments
• The SAT-UNSAT transition for random constraint satisfaction problems
• Phase transition for local search on planted SAT
• On the complexity of random satisfiability problems with planted solutions
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• Solving non-uniform planted and filtered random SAT formulas greedily
• Random MAX SAT, random MAX CUT, and their phase transitions
• scientific article; zbMATH DE number 2079360
• A Stochastic Limit Approach to the SAT Problem

Cites work

• 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?)
• 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
• Phase transitions and the search problem
• The TSP phase transition
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(4)

• SAT Distributions with Phase Transitions between Decision and Optimization Problems
• scientific article; zbMATH DE number 7306863 (Why is no real title available?)
• The planted matching problem: phase transitions and exact results
• 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 planted assignments and 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 Q2581547)