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

DOI10.1016/J.DAM.2005.05.006zbMATH Open1091.68059OpenAlexW2072912079MaRDI QIDQ2581547FDOQ2581547

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

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

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)

Cites Work

• Title not available (Why is that?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The TSP phase transition
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Title not available (Why is that?)
• A study of complexity transitions on the asymmetric traveling salesman problem
• Title not available (Why is that?)
• Determining computational complexity from characteristic ``phase transitions
• Title not available (Why is that?)
• Phase transitions and the search problem

Cited In (4)

• SAT Distributions with Phase Transitions between Decision and Optimization Problems
• Title not available (Why is that?)
• The planted matching problem: phase transitions and exact results
• A wealth of SAT distributions with planted assignments

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)