Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic (Q4864743)
From MaRDI portal
scientific article; zbMATH DE number 846580
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic |
scientific article; zbMATH DE number 846580 |
Statements
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic (English)
0 references
25 February 1996
0 references
Boolean function complexity
0 references
circuit size
0 references
SATISFIABILITY
0 references
bounded arithmetic
0 references
strong pseudorandom generators
0 references
