The Non-Hardness of Approximating Circuit Size
The Non-Hardness of Approximating Circuit Size
复制标题
近似电路尺寸的非困难性
DOI：
10.1007/978-3-030-19955-5_2
复制
发表时间：
2021
影响因子：
0.5
通讯作者：
Vafa, Neekon
中科院分区：
文献类型：
--
作者：
Allender, Eric;Ilango, Rahul;Vafa, Neekon
最小电路尺寸问题（MCSP）是近年来研究的热点。mcsp4在相当强大的约简下是很难实现的（Allender and Das Inf. compute . 256,2 - 8,2017），并且在可计算的“局部”约简下（n0.49）可以证明是不难的（Murray and Williams Theory compute .13(1), 1 - 22,2017）。在一些更熟悉的可约性概念（如多项式时间或inAC0可计算的多一元或图灵约简）下，mcspisnp -hard（或者实际上，对于p的小子类）是否困难的问题与复杂性理论中许多长期存在的开放问题密切相关。第一版。理论11(4),27:1-27:27,2019；阿伦德等人。第一版。高分子学报，26(2),469-496,2017；Hirahara and Santhanam 2017；平原和渡边2016；希区柯克和帕万2015；Impagliazzo et al. 2018；Murray and Williams理论计算，13(1),1 - 22,2017)。所有先前的硬度结果formcspo也适用于计算函数的电路复杂性的一些弱近似值（Allender等）。[j] .计算机工程学报，35(6),1467-1493,2006；杨志强，刘志强，刘志强，等。计算机工程学报，2016,33 (2):481 - 481；阿伦德等人。j .第一版。系统。科学通报，2011 (1):14-40；Hirahara and Santhanam 2017；Kabanets and Cai 2000；鲁氏过程。（在我们的工作之后，一个新的硬度结果已经公布（Ilango 2020），它依赖于更精确的尺寸计算）。其中一些结果是通过利用与有时Kolmogorov复杂度（KT）和相应的决策问题（MKTP）的概念的联系来证明的。最近，开发了一种新的方法来证明改进的硬度结果formktp （Allender等人）。[j] .计算机工程学报，2016,33 (4):1339-1372；平原和阿伦德，ACM译。第一版。理论11(4),27:1-27:27,2019)，但这种方法只建立了非常接近形式1 +o(1)的硬度，并且这些改进的硬度结果尚不知道是否适用于forMCSP。特别是，在非均匀约简下，mktpi对于复杂性类dett是困难的，这意味着mktpi对于任何素数（Allender and Hirahara ACM Trans.）都不是inAC0[p]。第一版。理论11(4),27:1-27:27,2019)。如果类似的电路下限保持forMCSP，它仍然是打开的（但参见Golovnev et al. 2019; Ilango 2020）。证明类似硬度结果formcsp的一个可能途径是将近似formktp的硬度从1 + 0(1)提高到ω(1)，因为复杂度和电路尺寸是多项式相关的。在本文中，我们证明了这种方法是不能成功的。更具体地说，我们证明parity不会通过进行eo(1)查询的ac0 -图灵约简来简化计算超线性近似tokt -复杂度或电路尺寸的问题。这是很重要的，因为近似p / polyac0中的任何集合都可以减少到对电路尺寸和kt复杂度的更差近似的查询（Oliveira和Santhanam 2017）。对于较弱的近似，我们也证明了在更强的约简下的非硬度。我们的非硬度结果是无条件的，与Allender和Hirahara （ACM Trans.）提出的条件结果相反。第一版。理论11(4),27:1-27:27,2019)（用于更强大的缩减，但用于更糟糕的近似）。这突出了必须克服的障碍，因为任何证据都表明mktpormcsp0难以实现npunderac0削减。这也可能是证实Murray和Williams猜想的一步，即mcsp在对数时间均匀化下不是tnp完备的。
The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently;MCSPis hard forSZKunder rather powerful reductions (Allender and Das Inf. Comput.256, 2–8, 2017), and is provably not hard under “local” reductions computable inTIME(n0.49) (Murray and Williams Theory Comput.13(1), 1–22, 2017). The question of whetherMCSPisNP-hard (or indeed, hard even for small subclasses ofP) under some of the more familiar notions of reducibility (such as many-one or Turing reductions computable in polynomial time or inAC0) is closely related to many of the longstanding open questions in complexity theory (Allender and Hirahara ACM Trans. Comput. Theory11(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 forMCSPhold 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 forMKTPwas developed (Allender et al. SIAM J. Comput.47(4), 1339–1372, 2018; Allender and Hirahara ACM Trans. Comput. Theory11(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 forMCSP. In particular, it is known thatMKTPis hard for the complexity classDETunder nonuniformreductions, implyingMKTPis not inAC0[p] for any primep(Allender and Hirahara ACM Trans. Comput. Theory11(4), 27:1–27:27, 2019). It was still open if similar circuit lower bounds hold forMCSP(But see Golovnev et al. 2019; Ilango 2020). One possible avenue for proving a similar hardness result forMCSPwould be to improve the hardness of approximation forMKTPbeyond 1 +o(1) toω(1), asKT-complexity and circuit size are polynomially-related. In this paper, we show that this approach cannot succeed. More specifically, we prove thatPARITYdoes not reduce to the problem of computing superlinear approximations toKT-complexity or circuit size viaAC0-Turing reductions that makeO(1) queries. This is significant, since approximating any set inP/polyAC0-reduces to justonequery of a much worse approximation of circuit size orKT-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. Theory11(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 thatMKTPorMCSPis hard forNPunderAC0reductions. It may also be a step toward confirming a conjecture of Murray and Williams, thatMCSPis notNP-complete under logtime-uniformreductions.