首页    期刊浏览 2025年04月30日 星期三
登录注册

文章基本信息

  • 标题:The Complexity of Debate Checking
  • 本地全文:下载
  • 作者:Gökalp Demirci ; A. C. Cem Say ; Abuzer Yakaryilmaz
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of the messages of the refuter, as well as those of complete information. This model combines and generalizes the concepts of one-way interactive proof systems, games of possibly incomplete information, and probabilistically checkable debate systems.

  • 关键词:incomplete information debates; probabilistic computation; games; private alternation
国家哲学社会科学文献中心版权所有