Derandomization and distinguishing complexity
Derandomization and distinguishing complexity
复制标题
去随机化和区分复杂性
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Sambuddha Roy
中科院分区：
文献类型：
--
作者：
Eric Allender;M. Koucký;Detlef Ronneburger;Sambuddha Roy
我们继续研究资源受限的Kolmogorov复杂性和去随机化技术，这些技术始于[E.Allender(2001)，E.Allender等人，(2002)]。我们引入了不确定的时间有界Kolmogorov复杂性度量(KNT和KNT)，并通过构造不确定电路的命中集生成器来研究这些度量的性质[P.B.Miltersen等人，(1999)，R.Shaltiel等人，(2001)]。我们观察到KNT与[H.Buhrman等人，(2002)]的非确定性区分复杂性CND有许多相似之处。这激发了时间受限区分复杂性KDT的新概念的定义，作为与类FewEXP相联系的中间概念。在P/Poly约简下，KdT-随机串的集合对于Exp是完备的。这里和[E.Allender(2001)，E.Allender等人(2002)]中讨论的大多数资源受限Kolmogorov复杂性的概念都与电路大小(在不同类型的电路上)密切相关。我们对该框架进行了扩展，定义了分别与分支程序大小和公式大小相关的Kolmogorov复杂性Kb和Kf的概念。Kb-和Kf-随机串的集合位于coNP中；我们证明了Oracle对这些集合的访问使人们能够因式分解Blum整数。我们得到了近似最小公式规模、分支程序规模和电路规模的相关难解结果。证明了NEXP/SPL Sube/NC和NEXP/SPL Sube/L/Poly问题等价于P中集合的KF和KB复杂性条件。
We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [E. Allender (2001), E. Allender et al., (2002)]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits [P. B. Miltersen et al., (1999), R. Shaltiel et al., (2001)]. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity CND of [H. Buhrman et al., (2002)]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in [E. Allender (2001), E. Allender et al., (2002)] have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP/spl sube/NC and NEXP/spl sube/L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.