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

DOI10.1016/j.dam.2005.05.006zbMath1091.68059OpenAlexW2072912079MaRDI QIDQ2581547

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

decision problemsassignment

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Uses Software

• Walksat

Cites Work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The TSP phase transition
• Phase transitions and the search problem
• 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’
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: SAT distributions with planted assignments and phase transitions between decision and optimization problems