The Non-hardness of Approximating Circuit Size

• Published in: Theory of computing systems 2021-04, Vol.65 (3), p.559-578
• Main Authors: Allender, Eric, Ilango, Rahul, Vafa, Neekon
• Format: Article
• Language: English
• Subjects: Approximation; Circuits; Complexity theory; Computation; Computer Science; Hardness; Lower bounds; Mathematical analysis; Polynomials; Questions; Special Issue on Computer Science Symposium in Russia; Theory of Computation
• ISSN: 1432-4350; 1433-0490
• DOI: 10.1007/s00224-020-10004-x

The Minimum Circuit Size Problem ( M C S P ) has been the focus of intense study recently; M C S P is hard for S Z K under rather powerful reductions (Allender and Das Inf. Comput. 256 , 2–8, 2017 ), and is provably not hard under “local” reductions computable in T I M E ( n 0.49 ) (Murray and Williams Theory Comput. 13 (1), 1–22, 2017 ). The question of whether M C S P is N P -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 A C 0 ) 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 M C S P 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 ( K T ) and the corresponding decision problem ( M K T P ). More recently, a new approach for proving improved hardness results for M K T P 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 M C S P . In particular, it is known that M K T P is hard for the complexity class D E T under nonuniform ≤ m A C 0 reductions, implying M K T P is not in A C 0 [ 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 M C S P (But see Golovnev et al. 2019 ; Ilango 2020 ). One possible avenue for proving a similar hardness result for M C S P would b