见证对称选择严格强于带计数的无选择多项式时间
Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究带计数的无选择多项式时间（choiceless polynomial time with counting）的表达力。作者声称证明见证对称选择严格增强其表达力：存在一个含单次见证选择出现的固定句子，在每个有限输入上定义布尔查询，而该查询不能在原计数形式主义中定义。若成立，将为该计算模型增加选择算子后的表达力差异提供分离结果。
- 比较带计数的无选择多项式时间与加入见证对称选择后的表达力。
- 作者声称存在固定句子定义的布尔查询无法在原形式主义中定义。
- 结论为见证对称选择严格增强该计数形式主义的表达力。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that witnessed symmetric choice strictly increases the expressive power of choiceless polynomial time with counting. A fixed sentence with one witnessed-choice occurrence defines a Boolean query on every finite input that is not definable in the original counting formalism.
用户标记：未标记
固定编号：076b2ad38161ab8b
原文来源