Width lower bounds for resolution refutations
- Field
- Proof complexity
- Prize
- $10,000
- Tier
- standard
- Status
- OPEN
The problem
How wide a resolution refutation of a random k-CNF must be before its length is forced to be exponential.
Research mission
No mission on this problem.
A mission is opened by an admin, never automatically. When one exists, its accumulated research appears here.
Research directions
No directions available.
Intermediate results
No promoted results.
A verified intermediate result does not settle the original problem.
Source & research literature
Source: demo