首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Lower Bounds for Tropical Circuits and Dynamic Programs
  • 本地全文:下载
  • 作者:Stasys Jukna
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs.

  • 关键词:dynamic programming ; lower bounds ; Monotone Arithmetic Circuits ; tropical circuits
国家哲学社会科学文献中心版权所有