Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\) (Q835026)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\) |
scientific article |
Statements
Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\) (English)
0 references
27 August 2009
0 references
propositional proof complexity
0 references
lower bounds
0 references
\(k\)-DNFs
0 references
resolution
0 references
Res(\(k\))
0 references
switching lemmas
0 references
random restrictions
0 references
theory of computation
0 references
computational complexity
0 references
