Sharp threshold results for computational complexity
© 2020 ACM. We establish several "sharp threshold" results for computational complexity. For certain tasks, we can prove a resource lower bound of nc for c ≥ 1 (or obtain an efficient circuit-analysis algorithm for nc size), there is strong intuition that a similar result can be proved for...
| Format: | Article |
|---|---|
| Language: | English |
| Published: |
ACM
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137205 |