下载PDF摘要：在20世纪80年代后期，Gurevich猜测没有逻辑捕获PTIME，其中逻辑必须以非常一般的方式理解，包括结构同构类上的计算模型。在这篇文章中，我们首先证明Gurevich的猜想是错误的。为此，我们扩展了Blass，Gurevich和Shelah在{eM无选择多项式时间}(CPT)上的半研究，它利用支持无界并行的确定性抽象状态机(ASM)来捕捉ptime的无选择片段。CPT严格包含在ptime中。我们观察到选择是不可避免的，但受限的版本就足够了，这就保证了最终的结果是独立于选择的。这样一种多项式有界的ASM，我们称之为{\em无关紧要的选择多项式时间}(ICPT)确实会捕获PTIME。这可以在非确定性ASM加膨胀定点的逻辑中表达出来。我们将这一结果用于我们的第二个贡献，表明ptime不同于np。为了证明这一点，我们再次建立在CPT研究的基础上，首先对可以通过ICPT计算激活的集合的置换类建立一个限制。然后，我们证明了一个等价定理，它刻画了逻辑无法区分的结构。特别是，它简化了SAT不能由ICPT计算来决定。