文章基本信息
- 标题：One-Tape Turing Machine and Branching Program Lower Bounds for MCSP
- 本地全文：下载
- 作者：Cheraghchi, Mahdi ; Hirahara, Shuichi ; Myrisiotis, Dimitrios 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2021
- 卷号：187
- 页码：23:1-23:19
- DOI：10.4230/LIPIcs.STACS.2021.23
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：For a size parameter s: â". â' â"., the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}â¿ â' {0,1} (represented by a string of length N : = 2â¿) is at most a threshold s(n). A recent line of work exhibited "hardness magnification" phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant μâ, > 0, if MCSP[2^{μâ,â μâ,. 2) A non-deterministic (or parity) branching program of size o(N^{1.5}/log N) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the NeÄiporuk method to MKTP, which previously appeared to be difficult. 3) The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least N^{1.5-o(1)}. These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola 2019). En route, we obtain several related results: 1) There exists a (local) hitting set generator with seed length OÌf(â^SN) secure against read-once polynomial-size non-deterministic branching programs on N-bit inputs. 2) Any read-once co-non-deterministic branching program computing MCSP must have size at least 2^ΩÌf(N).
- 关键词：Minimum Circuit Size Problem; Kolmogorov Complexity; One-Tape Turing Machines; Branching Programs; Lower Bounds; Pseudorandom Generators; Hitting Set Generators
