Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT

DOI10.1080/09720529.2020.1711602OpenAlexW3034683615MaRDI QIDQ5034546

Hera Antonopoulou

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

zbMATH Keywords

Kolmogorov complexityrandom formulaeunsatisfiability threshold of random formulae

Mathematics Subject Classification ID

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