• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Algorithms for Circuits and Circuits for Algorithms
【24h】

Algorithms for Circuits and Circuits for Algorithms

机译：用于算法电路和电路的算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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."
机译：本文的标题是为了强调在算法和复杂性理论的两个基本主题之间出现双重性。对于电路}算法指的是其中可以一个电路或给出的真值表的布尔函数上执行某种非平凡的电路分析中，有趣的算法的设计。例如，一种算法确定给定电路是否具有的力的真输出将解决NP完全电路-SAT问题的输入。这种算法当然不可能在多项式时间内运行，但能比试图穷尽所有可能的输入电路更有效。对于算法电路指的均匀算法具有非均匀电路家族（或证明这样的建模是不可能的）的建模。例如，相对于NEXP P /聚问题询问是否非确定性指数时间算法可使用多项式大小的不均匀电路的家庭来模拟。人们普遍认为，答案是EMPH {}没有，但可在本数学工具仍然太粗，以证明这种分离。已经开发他们之间，专注于非平凡的电路分析算法和电路尺寸下限的证据之间的联系本文综述这两个通用的科目，在其发生的方式和连接。举一个例子，如果存在一个非平凡算法（略快于穷举搜索运行），可确定给定的电路计算出一个恒定的功能，那么可以得出结论，NEXP不包含在P /聚。通俗地说，这方面可以理解为说：“对于电路一些好的算法意味着没有好的电路的一些算法。”

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号