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

DOI10.1080/09720529.2020.1711602MaRDI QIDQ5034546zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Approximating the unsatisfiability threshold of random formulas
• The unsatisfiability threshold revisited
• Approximating the unsatisfiability threshold of random formulas (extended abstract)

Cites work

• A formal theory of inductive inference. Part I
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• A new upper bound for 3-SAT
• An introduction to Kolmogorov complexity and its applications
• Approximating the unsatisfiability threshold of random formulas (extended abstract)
• Bounding the unsatisfiability threshold of random 3-SAT
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Lower bounds for random 3-SAT via differential equations
• Many hard examples for resolution
• On the Length of Programs for Computing Finite Binary Sequences
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Random MAX SAT, random MAX CUT, and their phase transitions
• Sharp thresholds of graph properties, and the k-sat problem
• Tail bounds for occupancy and the satisfiability threshold conjecture
• The probabilistic analysis of a greedy satisfiability algorithm
• The unsatisfiability threshold revisited

Cited in

(8)

• Random k-sat: the limiting probability for satisfiability for moderately growing k
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Approximating the unsatisfiability threshold of random formulas
• Bounding the unsatisfiability threshold of random 3-SAT
• scientific article; zbMATH DE number 1929945 (Why is no real title available?)
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The asymptotic k-SAT threshold

This page was built for publication: Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5034546)