辩论机制只需少量检查即可验证复杂任务，效率惊人。
Debate is efficient with your time
- 提出辩论查询复杂度衡量人类验证所需最少检查量
- 复杂问题仅需对数级查询即可正确判断
- 适合关注AI安全与验证效率的研究者
通过两个竞争模型辅助人类裁判验证复杂计算任务的辩论机制，已证明在理论上可解决某些问题，但缺乏对实际人力成本的分析：裁判需多少次查询才能正确判断辩论结果？本文引入辩论查询复杂度（DQC），即验证者为正确决策必须检查的最少比特数。令人惊讶的是，我们发现可被高效辩论解决的问题类（PSPACE/poly）恰好对应于仅需O(log n)次查询即可判定的函数类。该刻画表明辩论具有极高的查询效率：即使面对高度复杂的任务，对数级监督也足够。我们还证明，依赖所有输入位的函数至少需要Ω(log n)次查询；且任何由大小为s的电路计算的函数满足DQC(f) ≤ log(s) + 3。有趣的是，若能为P中语言证明DQC下界log(n) + 6，将带来电路复杂性领域的新下界，揭示了辩论查询复杂度与核心电路复杂性问题的深层联系。
原文摘要 · Abstract (English)
AI safety via debate uses two competing models to help a human judge verify complex computational tasks. Previous work has established what problems debate can solve in principle, but has not analysed the practical cost of human oversight: how many queries must the judge make to the debate transcript? We introduce Debate Query Complexity}(DQC), the minimum number of bits a verifier must inspect to correctly decide a debate. Surprisingly, we find that PSPACE/poly (the class of problems which debate can efficiently decide) is precisely the class of functions decidable with O(log n) queries. This characterisation shows that debate is remarkably query-efficient: even for highly complex problems, logarithmic oversight suffices. We also establish that functions depending on all their input bits require Omega(log n) queries, and that any function computable by a circuit of size s satisfies DQC(f) <= log(s) + 3. Interestingly, this last result implies that proving DQC lower bounds of log(n) + 6 for languages in P would yield new circuit lower bounds, connecting debate query complexity to central questions in circuit complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。