Name
Abstract | ||
|---|---|---|
The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deal with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) within a factor of n1 − o(1) is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function. Our technique is quite general; we use it also to show that approximating the size of the largest clique in a graph within a factor of n1 − o(1) is also NP-intermediate unless NP⊆ P/poly.
We also prove that MKTP is hard for the complexity class DET under non-uniform NC0 reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of “local” reductions such as ≤ NC0m. We exploit this local reduction to obtain several new consequences:
— MKTP is not in AC0[p].
— Circuit size lower bounds are equivalent to hardness of a relativized version MKTPA of MKTP under a class of uniform AC0 reductions, for a significant class of sets A.
— Hardness of MCSPA implies hardness of MCSPA for a significant class of sets A. This is the first result directly relating the complexity of MCSPA and MCSPA, for any A.
|
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3349616 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
Computational complexity,Kolmogorov complexity,MCSP,circuit size | Discrete mathematics,Algebra,Circuit minimization for Boolean functions,Mathematics | Journal |
Volume | Issue | ISSN |
11 | 4 | 1942-3454 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Allender | 1 | 1434 | 121.38 |
| Shuichi Hirahara | 2 | 7 | 3.48 |