Easily refutable subformulas of large random 3CNF formulas

DOI10.1007/978-3-540-27836-8_45MaRDI QIDQ5466490zbMATH OpenOpenAlexFDO

Authors Eran Ofek, Uriel Feige

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• scientific article; zbMATH DE number 5899254
• scientific article; zbMATH DE number 1775444
• Note on strong refutation algorithms for random \(k\)-SAT formulas
• Refuting random 3CNF formulas in propositional logic
• Recognizing more random unsatisfiable 3-SAT instances efficiently

Cited in

(12)

• On good algorithms for determining unsatisfiability of propositional formulas
• The efficiency of resolution and Davis-Putnam procedures
• Note on strong refutation algorithms for random \(k\)-SAT formulas
• scientific article; zbMATH DE number 5899254 (Why is no real title available?)
• Random k-SAT and the power of two choices
• Approximation algorithms for discrete polynomial optimization
• scientific article; zbMATH DE number 1775444 (Why is no real title available?)
• On the complexity of random satisfiability problems with planted solutions
• On minrank and the Lovász theta-function
• Sparser random 3-SAT refutation algorithms and the interpolation problem (extended abstract)
• On sufficient conditions for unsatisfiability of random formulas
• Sufficient condition for polynomial solvability of random 3-CNF formulas

This page was built for publication: Easily refutable subformulas of large random 3CNF formulas

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