𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Resolution lower bounds for perfect matching principles

✍ Scribed by Alexander A Razborov

Book ID
108166478
Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
353 KB
Volume
69
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Resolution lower bounds for the weak fun
Resolution lower bounds for the weak functional pigeonhole principle
✍ Alexander A. Razborov πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 243 KB

We show that every resolution proof of the functional version FPHP m n of the pigeonhole principle (in which one pigeon may not split between several holes) must have size exp( (n=(log m) 2 )). This implies an exp( (n 1=3 )) bound when the number of pigeons m is arbitrary.