Circuit lower bounds from NP-hardness of MCSP under turing reductions
Circuit lower bounds from NP-hardness of MCSP under turing reductions
复制标题
图灵约简下 MCSP NP 硬度的电路下界
DOI：
10.4230/lipics.ccc.2020.26
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
R. Santhanam
中科院分区：
文献类型：
--
作者：
M. Saks;R. Santhanam
基本的最小电路尺寸问题是一个众所周知的例子，既不知道是在P中，也不知道是NP难的问题。Kabanets和Cai [18]表明，如果MCSP在“自然”m-约简下是NP-难的，则指数时间的超多项式电路下界将遵循。这引发了一系列关于了解减少小额信贷支助项目的力量的工作。到目前为止，还没有人知道MCSP在一般图灵约化下的NP-硬度的后果。在这项工作中，我们考虑两种结构化的图灵约简：参数诚实约简和自然约简。后者将Kabanets和Cai的自然约化推广到图灵约化的情形。我们表明，NP-困难的MCSP下这些种图灵约简意味着指数时间的超多项式电路下界。
The fundamental Minimum Circuit Size Problem is a well-known example of a problem that is neither known to be in P nor known to be NP-hard. Kabanets and Cai [18] showed that if MCSP is NP-hard under "natural" m-reductions, superpolynomial circuit lower bounds for exponential time would follow. This has triggered a long line of work on understanding the power of reductions to MCSP. Nothing was known so far about consequences of NP-hardness of MCSP under general Turing reductions. In this work, we consider two structured kinds of Turing reductions: parametric honest reductions and natural reductions. The latter generalize the natural reductions of Kabanets and Cai to the case of Turing-reductions. We show that NP-hardness of MCSP under these kinds of Turing-reductions imply superpolynomial circuit lower bounds for exponential time.
影响因子：
1.4
作者：
Eric Allender;D. Holden;Valentine Kabanets
通讯作者：
Eric Allender;D. Holden;Valentine Kabanets