Disproof of the neighborhood conjecture with implications to SAT

DOI10.1007/S00493-012-2679-YMaRDI QIDQ377802zbMATH OpenOpenAlexWikidataFDO

Authors Heidi Gebauer

Publication date 7 November 2013

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.11850/61671

zbMATH Keywords

SATbinary tree

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Positional games (pursuit and evasion, etc.) (91A24)

Recommendations

• Disproof of the Neighborhood Conjecture with Implications to SAT
• The local lemma Is asymptotically tight for SAT
• The local lemma is tight for SAT
• On unavoidability of trees with k leaves
• scientific article; zbMATH DE number 1445296

Cites work

• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• A constructive proof of the Lovász local lemma
• A simplified NP-complete satisfiability problem
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Combinatorial Games
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• DNF tautologies with a limited number of occurrences of every variable
• Homomorphisms of conjunctive normal forms.
• Lopsided Lovász Local lemma and Latin transversals
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• On a combinatorial game
• On the structure of some classes of minimal unsatisfiable formulas
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Remarks on positional games. I
• The local lemma is tight for SAT
• Unsatisfiable linear CNF formulas are large and complex

Cited in

(5)

• The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant
• Small unsatisfiable k-CNFs with bounded literal occurrence
• Disproof of the Neighborhood Conjecture with Implications to SAT
• On the parameterized complexity of \((k,s)\)-SAT
• Comparison of two convergence criteria for the variable-assignment lopsided Lovász local lemma

This page was built for publication: Disproof of the neighborhood conjecture with implications to SAT

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