SAT Distributions with Phase Transitions between Decision and Optimization Problems

DOI10.1016/S1571-0653(04)00459-7zbMath1179.68140OpenAlexW1965034621MaRDI QIDQ3439111

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)

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 Phase Transitions between Decision and Optimization Problems