A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution (Q4651510)
From MaRDI portal
scientific article; zbMATH DE number 2135811
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution |
scientific article; zbMATH DE number 2135811 |
Statements
A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution (English)
0 references
21 February 2005
0 references
propositional proof complexity
0 references
Boolean circuit complexity
0 references
switching lemmas
0 references
lower bounds
0 references
\(k\)-DNFs
0 references
resolution
0 references
circuit bottom fan-in
0 references
random restriction
0 references
Sipser functions
0 references
weak pigeonhole principles
0 references
random CNFs
0 references
