Simplicity and Complexity in Combinatorial Optimization
Abstract
Many problems in physics and computer science can be framed in terms of combinatorial optimization. Due to this, it is interesting and important to study theoretical aspects of such optimization. Here, we study connections between Kolmogorov complexity, optima, and optimization. We argue that (1) optima and complexity are connected, with extrema being more likely to have low complexity (under certain circumstances); (2) optimization by sampling candidate solutions according to algorithmic probability may be an effective optimization method; and (3) coincidences in extrema to optimization problems are a priori more likely as compared to a purely random null model.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
Complexity and Algorithms in Graphs
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Entropy
- Publisher
- MDPI AG
- Volume
- 28
- Issue
- 2
- Pages
- 226–226
- Publication date
- 15 February 2026
- Language
- EN