Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques.
From MaRDI portal
Certifying unsatisfiability of random \(2k\)-SAT formulas using approximation techniques.
Recommendations
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
- scientific article; zbMATH DE number 1929945
- Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
Cited in
(6)- Approximating highly satisfiable random 2-SAT
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
- Exact and approximative algorithms for coloring G(n,p)
- Spectral techniques applied to sparse random graphs
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
This page was built for publication: Certifying unsatisfiability of random \(2k\)-SAT formulas using approximation techniques.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900782)
