The Non-hardness of Approximating Circuit Size
- PDF / 463,892 Bytes
- 20 Pages / 439.642 x 666.49 pts Page_size
- 15 Downloads / 220 Views
The Non-hardness of Approximating Circuit Size Eric Allender1
· Rahul Ilango2 · Neekon Vafa3,4
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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, This article belongs to the Topical Collection: Special Issue on Computer Science Symposium in Russia (2019) Guest Editor: Gregory Kucherov Eric Allender
[email protected]
Extended author information available on the last page of the article.
Theory of Computing Systems 0
it is known that MKTP is hard for the complexity class DET under nonuniform ≤AC m 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 speci
Data Loading...
