Approximating the unsatisfiability threshold of random formulas (extended abstract)

DOI10.1007/3-540-61680-2_44zbMATH Open1379.68172OpenAlexW1600826028MaRDI QIDQ4595474FDOQ4595474

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

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

Mathematics Subject Classification ID

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

Cited In (8)

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

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)