Disproof of the neighborhood conjecture with implications to SAT (Q377802)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Disproof of the neighborhood conjecture with implications to SAT |
scientific article |
Statements
Disproof of the neighborhood conjecture with implications to SAT (English)
0 references
7 November 2013
0 references
In a binary tree (a rooted tree whose nodes all have either 2 or 0 children) a leaf is \(\ell\)-close to a node if the node is an ancestor distant at most \(\ell\); a \((k,d)\)-tree is a binary tree in which every leaf has depth at least \(k-1\), and there are, for every node, at most \(d\) leaves which are \((k-1)\)-close. Lemma 1.1: A \(\left(k,\left\lfloor \frac{2^{k+2}}k\right\rfloor\right)\)-tree exists for every \(k\geq1\). The author advises in her introduction that this lemma ``will be the main ingredient in proving some new results on Maker/Breaker games and SAT'' (the ``Boolean satisfiability problem''). See also the detailed abstract of the author's paper [Lect. Notes Comput. Sci. 5757, 764--775 (2009; Zbl 1256.68083)].
0 references
binary tree
0 references
SAT
0 references