Disproof of the neighborhood conjecture with implications to SAT

DOI10.1007/S00493-012-2679-YzbMATH Open1289.68047OpenAlexW1782236248WikidataQ123017151 ScholiaQ123017151MaRDI QIDQ377802FDOQ377802

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

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
• Publication:4952609

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)

Cites Work

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

Cited In (5)

• The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant
• Unsplittable coverings in the plane
• Disproof of the Neighborhood Conjecture with Implications to SAT
• Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma
• On the parameterized complexity of \((k,s)\)-SAT

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)