Random CNF's are hard for the polynomial calculus (Q626686)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Random CNF's are hard for the polynomial calculus |
scientific article |
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
