Random CNF's are hard for the polynomial calculus (Q626686)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Random CNF's are hard for the polynomial calculus |
scientific article; zbMATH DE number 5853292
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Random CNF's are hard for the polynomial calculus |
scientific article; zbMATH DE number 5853292 |
Statements
Random CNF's are hard for the polynomial calculus (English)
0 references
18 February 2011
0 references
propositional proof complexity
0 references
polynomial calculus
0 references
Gröbner basis
0 references
random CNF formulae
0 references
lower bounds
0 references
refutation-degree
0 references
Gaussian width
0 references
complexity of refuting unsatisfiable systems of linear equations
0 references
0.88688904
0 references
0.85340154
0 references
0 references
0 references
