Circuit lower bounds from NP-hardness of MCSP under Turing reductions
The fundamental Minimum Circuit Size Problem is a well-known example of a problem that is neither known to be in P nor known to be NP-hard. Kabanets and Cai [18] showed that if MCSP is NP-hard under “natural" m-reductions, superpolynomial circuit lower bounds for exponential time would follow....
| Huvudupphovsmän: | , |
|---|---|
| Materialtyp: | Conference item |
| Språk: | English |
| Publicerad: |
Schloss Dagstuhl
2020
|