Approximating the unsatisfiability threshold of random formulas (Extended Abstract)

DOI10.1007/3-540-61680-2_44zbMath1379.68172OpenAlexW1600826028MaRDI QIDQ4595474

Lefteris M. Kirousis, Danny Krizanc, Evangelos Kranakis

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)

Related Items (4)

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 ⋮ Upper bounds on the satisfiability threshold ⋮ Complexity-theoretic models of phase transitions in search problems

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