首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:A note on semantic cutting planes
  • 本地全文:下载
  • 作者:Pavel Hrubes
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system.

    We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two variables?

  • 关键词:cutting planes; Feasible Interpolation
国家哲学社会科学文献中心版权所有