The Minimum Oracle Circuit Size Problem
The Minimum Oracle Circuit Size Problem
复制标题
DOI：
10.1007/s00037-016-0124-0
复制
发表时间：
2016-02
影响因子：
1.4
通讯作者：
Eric Allender;D. Holden;Valentine Kabanets
中科院分区：
文献类型：
--
作者：
Eric Allender;D. Holden;Valentine Kabanets
我们考虑最小电路尺寸问题MCSP的变体，其目标是最小化计算给定函数的尺寸ofacirclance。当预言机是QBF时，所得到的问题MSCPQBF已知在ZPP约化下对于PSPACE是完全的。我们证明了它在对数空间约化下是不完全的，而且在一致AC 0约化下对TC 0甚至不难。我们得到了各种后果，随后如果Oracle版本的MCSP是很难的各种复杂性类下不同类型的减少。我们还证明了类似的结果，确定资源有界的Kolmogorov复杂性的字符串的问题，对于某些类型的Kolmogorov复杂性措施。
We consider variants of the minimum circuit size problem MCSP, where the goal is to minimize the size oforaclecircuits computing a given function. When the oracle is QBF, the resulting problem MSCPQBFis known to be complete for PSPACE under ZPP reductions. We show that it isnotcomplete under logspace reductions, and indeed it is not even hard for TC0under uniform AC0reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures.