On the size of minimal unsatisfiable formulas
| dc.creator | Lee, Choongbum | |
| dc.date | 2008-11-04 | |
| dc.date.accessioned | 2026-07-07T10:15:20Z | |
| dc.date.available | 2026-07-07T10:15:20Z | |
| dc.description | An unsatisfiable formula is called minimal if it becomes satisfiable whenever any of its clauses are removed. We construct minimal unsatisfiable $k$-SAT formulas with $Ω(n^k)$ clauses for $k \geq 3$, thereby negatively answering a question of Rosenfeld. This should be compared to the result of Lovász which asserts that a critically 3-chromatic $k$-uniform hypergraph can have at most $\binom{n}{k-1}$ edges. | |
| dc.description | 4 pages | |
| dc.identifier | https://arxiv.org/abs/0811.0427 | |
| dc.identifier | http://arxiv.org/abs/0811.0427 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/173143 | |
| dc.subject | Combinatorics | |
| dc.title | On the size of minimal unsatisfiable formulas | |
| dc.type | text |