The Minimum Formula Size Problem is (ETH) Hard
The Minimum Formula Size Problem is (ETH) Hard
复制标题
最小公式大小问题（ETH）很难
DOI：
10.1109/focs52979.2021.00050
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Rahul Ilango
中科院分区：
文献类型：
--
作者：
Rahul Ilango
最小电路尺寸问题（MCSP）是否是NP完全问题是一个长期存在的问题。事实上，即使是确定MCSP是否具有搜索到决策的减少也已经开放了二十多年。我们发现，在指数时间假设下，最小（DeMorgan）公式大小问题，MFSP，是不是在P.在此基础上，我们表明，MFSP有一个多项式时间（精确）的搜索决策减少，结果不相对化。我们的主要技术涉及的公式复杂性的部分功能与相关的总功能的公式复杂性，并证明使用“叶加权”技术的Buchfuhrer和乌曼斯。
A longstanding open question is whether the Minimum Circuit Size Problem (MCSP) is NP-complete. In fact, even determining whether MCSP has a search-to-decision reduction has been open for over twenty years. We show that, under the Exponential Time Hypothesis, the Minimum (DeMorgan) Formula Size Problem, MFSP, is not in P. Building on this, we show that MFSP has a polynomial-time (exact) search-to-decision reduction, a result that does not relativize. Our main technique relates the formula complexity of a partial function with the formula complexity of an associated total function and is proved using the “leaf weighting” technique of Buchfuhrer and Umans.
DOI：
10.4230/lipics.stacs.2022.54
发表时间：
2021
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Hanlin Ren;R. Santhanam
通讯作者：
Hanlin Ren;R. Santhanam
AC0[p] 通过硬币问题针对 MCSP 的下界
DOI：
--
发表时间：
2019
期刊：
ICALP
影响因子：
--
作者：
Golovnev, Alexander;Ilango, Rahul;Impagliazzo, Russell;Kabanets, Valentine;Kolokolova, Antonina;Tal, Avishay
通讯作者：
Tal, Avishay
来自有时间限制的柯尔莫哥洛夫复杂度的亚线性时间平均情况硬度的密码学
DOI：
10.1145/3406325.3451121
发表时间：
2021
期刊：
ACM Symposium on Theory of Computing (STOC
影响因子：
--
作者：
Liu, Yanyi;Pass, Rafael
通讯作者：
Pass, Rafael