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....
| Egile Nagusiak: | , |
|---|---|
| Formatua: | Conference item |
| Hizkuntza: | English |
| Argitaratua: |
Schloss Dagstuhl
2020
|