标题： 逻辑方法在半环上的非确定性多项式时间 显示英文标题

标题： Logical Approaches to Non-deterministic Polynomial Time over Semirings

摘要： 我们通过存在性二阶逻辑在Grädel和Tannen开发的半环语义中进行解释，提供了通过BSS机器在半环上定义的非确定性多项式时间的逻辑特征。 此外，我们证明了类似于经典情况，命题逻辑在半环语义中的可满足性问题是这种NP版本的规范完全问题。 最终，我们证明了半环的存在性一阶理论是这种NP版本所谓的布尔部分的完全问题。 显示英文摘要

摘要： We provide a logical characterization of non-deterministic polynomial time defined by BSS machines over semirings via existential second-order logic interpreted in the semiring semantics developed by Gr\"adel and Tannen. Furthermore, we show that, similarly to the classical setting, the satisfiability problem of propositional logic in the semiring semantics is the canonical complete problem for this version of NP. Eventually, we prove that the true existential first-order theory of the semiring is a complete problem for the so-called Boolean part of this version of NP.