Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT
From MaRDI portal
Publication:5034546
DOI10.1080/09720529.2020.1711602OpenAlexW3034683615MaRDI QIDQ5034546
Publication date: 18 February 2022
Published in: Journal of Discrete Mathematical Sciences and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/09720529.2020.1711602
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Cites Work
- Unnamed Item
- Unnamed Item
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- The unsatisfiability threshold revisited
- A new upper bound for 3-SAT
- Many hard examples for resolution
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Bounding the unsatisfiability threshold of random 3-SAT
- Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
- Random MAX SAT, random MAX CUT, and their phase transitions
- Tail bounds for occupancy and the satisfiability threshold conjecture
- The probabilistic analysis of a greedy satisfiability algorithm
- On the Length of Programs for Computing Finite Binary Sequences
- A formal theory of inductive inference. Part I
- An introduction to Kolmogorov complexity and its applications
- Lower bounds for random 3-SAT via differential equations
This page was built for publication: Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT