Explaining the Ubiquity of Phase Transitions in Decision Problems

2025/01/24 by Andrew Jackson, Jackson, Andrew · 1 citation
Computer Science · #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2501.14569

openalex publication_date 2025/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

I present an analytic approach to establishing the presence of phase transitions in a large set of decision problems. This approach does not require extensive computational study of the problems considered. The set -- that of all paddable problems over even-sized alphabets satisfying a condition similar to not being sparse -- shown to exhibit phase transitions contains many "practical" decision problems, is very large, and also contains extremely intractable problems.

Cited by

• Phase Transitions in Decision Problems Over Odd-Sized Alphabets

Related

• Phase Transitions in Decision Problems Over Odd-Sized Alphabets
• 2+p-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition
• Phase transition in the knapsack problem
• Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity
• Analytic Description of the Phase Transition of Inhomogeneous Multigraphs