Approximating the unsatisfiability threshold of random formulas (extended abstract)

DOI10.1007/3-540-61680-2_44MaRDI QIDQ4595474zbMATHOpenAlexFDO

Authors L. M. Kirousis, Evangelos Kranakis, D. Krizanc

Publication date 5 December 2017

Published in Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL https://ir.library.carleton.ca/pub/9061

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Approximating the unsatisfiability threshold of random formulas
• The unsatisfiability threshold revisited
• scientific article; zbMATH DE number 1114008
• Bounding the unsatisfiability threshold of random 3-SAT
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))

Cited in

(8)

• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Upper bounds on the satisfiability threshold
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• On unique satisfiability and the threshold behavior of randomized reductions
• A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
• Complexity-theoretic models of phase transitions in search problems

This page was built for publication: Approximating the unsatisfiability threshold of random formulas (extended abstract)

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