带计数的无选择多项式时间不能刻画多项式时间
Choiceless polynomial time with counting does not capture polynomial time
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件声称证明了带计数的无选择多项式时间在无序有限结构上不能刻画多项式时间，从而证实Blass、Gurevich与Shelah提出的非刻画猜想。摘要表示，在一个固定二元词汇表上关于𝔽3的线性一致性查询可在多项式时间内判定，但不能在完整计数形式体系中表达。研究对象属于有限模型论与描述复杂性；手稿为AI产生，未经独立审查或同行评议。
- 声称带计数的无选择多项式时间不刻画多项式时间
- 给出𝔽3上线性一致性查询作为分离例子
- 证实Blass–Gurevich–Shelah非刻画猜想
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that choiceless polynomial time with counting does not capture polynomial time on unordered finite structures, confirming the noncapture conjecture of Blass, Gurevich and Shelah. A linear-consistency query over 𝔽3 in a fixed binary vocabulary is decidable in polynomial time but not in the full counting formalism.
用户标记：未标记
固定编号：791aa94f5608bb5a
原文来源