Circuit-size lower bounds and non-reducibility to sparse sets (Q3323851)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Circuit-size lower bounds and non-reducibility to sparse sets |
scientific article |
Statements
Circuit-size lower bounds and non-reducibility to sparse sets (English)
0 references
1982
0 references
Boolean circuit
0 references
circuit-size
0 references
reducibility to sparse sets
0 references
polynomial-time hierarchy
0 references
NP
0 references