The Minimum Circuit Size Problem (
MCSP) has been the focus of intense study recently;
MCSP is hard for
SZK under rather powerful reductions (Allender and Das Inf. Comput.
256, 2–8,
2017), and is provably not hard under “local” reductions computable in
TIME(
n0.49) (Murray and Williams Theory Comput.
13(1), 1–22,
2017). The question of whether
MCSP is
NP-hard (or indeed, hard even for small subclasses of
P) under some of the more familiar notions of reducibility (such as many-one or Turing reductions computable in polynomial time or in
AC0) is closely related to many of the longstanding open questions in complexity theory (Allender and Hirahara ACM Trans. Comput. Theory
11(4), 27:1–27:27,
2019; Allender et al. Comput. Complex.
26(2), 469–496,
2017; Hirahara and Santhanam
2017; Hirahara and Watanabe
2016; Hitchcock and Pavan
2015; Impagliazzo et al.
2018; Murray and Williams Theory Comput.
13(1), 1–22,
2017). All prior hardness results for
MCSP hold also for computing somewhat weak approximations to the circuit complexity of a function (Allender et al. SIAM J. Comput. 35(6), 1467–1493,
2006; Allender and Das Inf. Comput.
256, 2–8,
2017; Allender et al. J. Comput. Syst. Sci.
77(1), 14–40,
2011; Hirahara and Santhanam
2017; Kabanets and Cai
2000; Rudow Inf. Process. Lett.
128, 1–4,
2017) (Subsequent to our work, a new hardness result has been announced (Ilango
2020) that relies on more exact size computations). Some of these results were proved by exploiting a connection to a notion of time-bounded Kolmogorov complexity (
KT) and the corresponding decision problem (
MKTP). More recently, a new approach for proving improved hardness results for
MKTP was developed (Allender et al. SIAM J. Comput.
47(4), 1339–1372,
2018; Allender and Hirahara ACM Trans. Comput. Theory
11(4), 27:1–27:27,
2019), but this approach establishes only hardness of extremely good approximations of the form 1 +
o(1), and these improved hardness results are not yet known to hold for
MCSP. In particular, it is known that
MKTP is hard for the complexity class
DET under nonuniform
\(\leq _{\text {m}}^{\mathsf {AC}^{0}}\) reductions, implying
MKTP is not in
AC0[
p] for any prime
p (Allender and Hirahara ACM Trans. Comput. Theory
11(4), 27:1–27:27,
2019). It was still open if similar circuit lower bounds hold for
MCSP (But see Golovnev et al.
2019; Ilango
2020). One possible avenue for proving a similar hardness result for
MCSP would be to improve the hardness of approximation for
MKTP beyond 1 +
o(1) to
ω(1), as
KT-complexity and circuit size are polynomially-related. In this paper, we show that this approach cannot succeed. More specifically, we prove that
PARITY does not reduce to the problem of computing superlinear approximations to
KT-complexity or circuit size via
AC0-Turing reductions that make
O(1) queries. This is significant, since approximating any set in
P/poly AC0-reduces to just
one query of a much worse approximation of circuit size or
KT-complexity (Oliveira and Santhanam
2017). For weaker approximations, we also prove non-hardness under more powerful reductions. Our non-hardness results are unconditional, in contrast to conditional results presented in Allender and Hirahara (ACM Trans. Comput. Theory
11(4), 27:1–27:27,
2019) (for more powerful reductions, but for much worse approximations). This highlights obstacles that would have to be overcome by any proof that
MKTP or
MCSP is hard for
NP under
AC0 reductions. It may also be a step toward confirming a conjecture of Murray and Williams, that
MCSP is not
NP-complete under logtime-uniform
\(\leq _{\text {m}}^{\mathsf {AC}^{0}}\) reductions.