Algorithms for Circuits and Circuits for Algorithms
Algorithms for Circuits and Circuits for Algorithms
复制标题
电路的算法和算法的电路
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
Ryan Williams
这篇论文的标题是为了强调算法和复杂性理论中的两个基本主题之间正在出现的二元性。电路的算法指的是有趣的算法的设计，这些算法可以对作为真值表给出的电路或布尔函数执行某种类型的非平凡电路分析。例如，确定给定电路是否具有强制真输出的输入的算法将解决NP-Complete电路-SAT问题。当然，这样的算法不太可能在多项式时间内运行，但可能比穷尽地尝试电路的所有可能输入更有效。用于算法的电路指的是对具有非统一电路族的统一算法进行建模(或者证明这种建模是不可能的)。例如，NEXP与P/Polyy问题询问是否可以使用多项式大小的非均匀电路族来模拟不确定的指数时间算法。人们普遍认为答案是否定的，然而目前可用的数学工具仍然太粗糙，无法证明这种分离。本文综述了这两个一般学科，它们的产生方式，以及它们之间的联系，重点讨论了非平凡电路分析算法与电路大小下界证明之间的联系。举一个例子，如果有一个非平凡算法(运行速度略快于穷举搜索)可以确定给定电路是否计算一个常量函数，则可以得出结论，NEXP不包含在P/Poly中。非正式地，这种联系可以被解释为说“一些电路的好算法意味着对于一些算法没有好的电路。”
The title of this paper is meant to highlight an emerging duality between two fundamental topics in algorithms and complexity theory. Algorithms for circuits} refers to the design of interesting algorithms which can perform non-trivial circuit analysis of some kind, on either a circuit or a Boolean function given as a truth table. For instance, an algorithm determining whether a given circuit has an input that forces a true output would solve the NP-complete Circuit-SAT problem. Such an algorithm is of course unlikely to run in polynomial time, but could possibly be more efficient than exhaustively trying all possible inputs to the circuit. Circuits for algorithms refers to the modeling of uniform algorithms with non-uniform circuit families (or proving such modeling is impossible). For instance, the NEXP versus P/poly question asks whether nondeterministic exponential-time algorithms can be simulated using non-uniform circuit families of polynomial size. It is widely believed that the answer is emph{no}, however the present mathematical tools available are still too crude to prove this kind of separation. This paper surveys these two generic subjects, the ways in which they arise, and connections that have been developed between them, focusing on the connections between non-trivial circuit-analysis algorithms and proofs of circuit size lower bounds. To give one example, if there is a nontrivial algorithm (running slightly faster than exhaustive search) that can determine if a given circuit computes a constant function, then it can be concluded that NEXP is not contained in P/poly. Informally, this connection can be interpreted as saying "some good algorithms for circuits imply there are no good circuits for some algorithms."
关于介质均匀性和电路下界
DOI：
10.1109/ccc.2013.40
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Santhanam R
通讯作者：
Santhanam R