Recognizing more random unsatisfiable 3-SAT instances efficiently

DOI10.1016/S1571-0653(04)00461-5MaRDI QIDQ3439113zbMATH OpenFDO

Authors André Lanka, Andreas Goerdt

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S1571-0653(04)00461-5

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• scientific article; zbMATH DE number 1754601
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• scientific article; zbMATH DE number 1929945
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• scientific article; zbMATH DE number 1689045

Cites work

• Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques.
• scientific article; zbMATH DE number 1689045 (Why is no real title available?)
• scientific article; zbMATH DE number 637070 (Why is no real title available?)
• scientific article; zbMATH DE number 1754601 (Why is no real title available?)
• scientific article; zbMATH DE number 1929945 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Relations between average case complexity and approximation complexity
• Sharp thresholds of graph properties, and the k-sat problem
• Spectral techniques applied to sparse random graphs
• The eigenvalues of random symmetric matrices

Cited in

(11)

• On good algorithms for determining unsatisfiability of propositional formulas
• scientific article; zbMATH DE number 1689045 (Why is no real title available?)
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• scientific article; zbMATH DE number 1754601 (Why is no real title available?)
• On the complexity of random satisfiability problems with planted solutions
• Automata, Languages and Programming
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• On sufficient conditions for unsatisfiability of random formulas
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• Spectral refutations of semirandom k-LIN over larger fields
• Short propositional refutations for dense random 3CNF formulas

This page was built for publication: Recognizing more random unsatisfiable 3-SAT instances efficiently

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