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

文章基本信息

  • 标题:A Characterization of Tree-Like Resolution Size
  • 本地全文:下载
  • 作者:Olaf Beyersdorff ; Nicola Galesi ; Massimo Lauria
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We explain an asymmetric Prover-Delayer game which precisely characterizes proof size in tree-like Resolution. This game was previously described in a parameterized complexity context to show lower bounds for parameterized formulas and for the classical pigeonhole principle. The main point of this note is to show that the asymmetric game in fact characterizes tree-like Resolution proof size, i.e. in principle our proof method allows to always achieve the optimal lower bounds. This is in contrast with previous techniques described in the literature. We also provide a very intuitive information-theoretic interpretation of the game.

  • 关键词:Prover-Delayer Games; Resolution
国家哲学社会科学文献中心版权所有