Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]
复制标题
从上到下接近 MCSP：条件变体和 AC^0[p] 的硬度
DOI：
10.4230/lipics.itcs.2020.34
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rahul Ilango
中科院分区：
文献类型：
--
作者：
Rahul Ilango
最小电路尺寸问题（MCSP）询问给定的布尔函数是否具有至多给定尺寸的电路。 MCSP 的研究已经有半个多世纪了，它与整个理论计算机科学有着深厚的联系，包括密码学、计算学习理论和证明复杂性。例如，我们（非正式地）知道，如果 MCSP 易于计算，那么大多数密码学都可以被破解。尽管有这种密码学硬度联系和广泛的研究，我们对 MCSP 的硬度无条件了解仍然相对较少。事实上，直到最近，人们还不知道 MCSP 是否可以在 AC0[2] 中计算（Golovnev 等人，ICALP 2019）。我们在本文中的主要贡献是制定了一种新的电路复杂性“预言”变体，并证明该问题在随机约简下是 NP 完全的。更详细地说，我们定义了最小预言电路尺寸问题（MOCSP），它将布尔函数 f 的真值表、大小阈值 s 和预言布尔函数 O 的真值表作为输入，并确定是否存在具有 O 预言门和最多 s 条线路的电路来计算 f 。我们证明 MOCSP 在随机多项式时间约简下是 NP 完全的。我们还扩展了 Golovnev 等人最近针对 MCSP 的 AC0[p] 下限。到深度 d 公式 (ACd)-MCSP 的电路最小化问题的下界。我们认为这一结果主要是技术贡献。特别是，我们的证明采用了与之前 MCSP 相关硬度结果完全不同的方法。 2012年ACM学科分类 计算理论→电路复杂度；计算理论 → 问题、简化和完备性
The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function has a circuit of at most a given size. MCSP has been studied for over a half-century and has deep connections throughout theoretical computer science including to cryptography, computational learning theory, and proof complexity. For example, we know (informally) that if MCSP is easy to compute, then most cryptography can be broken. Despite this cryptographic hardness connection and extensive research, we still know relatively little about the hardness of MCSP unconditionally. Indeed, until very recently it was unknown whether MCSP can be computed in AC0[2] (Golovnev et al., ICALP 2019). Our main contribution in this paper is to formulate a new “oracle” variant of circuit complexity and prove that this problem is NP-complete under randomized reductions. In more detail, we define the Minimum Oracle Circuit Size Problem (MOCSP) that takes as input the truth table of a Boolean function f , a size threshold s, and the truth table of an oracle Boolean function O, and determines whether there is a circuit with O-oracle gates and at most s wires that computes f . We prove that MOCSP is NP-complete under randomized polynomial-time reductions. We also extend the recent AC0[p] lower bound against MCSP by Golovnev et al. to a lower bound against the circuit minimization problem for depth-d formulas, (ACd)-MCSP. We view this result as primarily a technical contribution. In particular, our proof takes a radically different approach from prior MCSP-related hardness results. 2012 ACM Subject Classification Theory of computation → Circuit complexity; Theory of computation → Problems, reductions and completeness
AC0[p] 通过硬币问题针对 MCSP 的下界
DOI：
--
发表时间：
2019
期刊：
ICALP
影响因子：
--
作者：
Golovnev, Alexander;Ilango, Rahul;Impagliazzo, Russell;Kabanets, Valentine;Kolokolova, Antonina;Tal, Avishay
通讯作者：
Tal, Avishay
影响因子：
1.4
作者：
Eric Allender;D. Holden;Valentine Kabanets
通讯作者：
Eric Allender;D. Holden;Valentine Kabanets
来自本地伪随机发生器的 MCSP 电路下界
影响因子：
0.7
作者：
Cheraghchi M
通讯作者：
Cheraghchi M