Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. The Minimum Circuit Size Problem (MCSP) asks to determine the minimum size of a circuit computing a given truth table. MCSP is a natural and powerful string compression problem whose NP-hardness remains open. Recently,...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137518 |