论文标题
真实计算和概率独立性逻辑的描述性复杂性
Descriptive complexity of real computation and probabilistic independence logic
论文作者
论文摘要
我们介绍了一种新颖的BSS机器变体，称为单独的分支BSS机器（简称S-BSS），并为在非确定性多项式时间内通过S-BSS机器确定的语言进行Fagin型逻辑表征。我们表明，S-BSS机器上的NP严格包含在BSS机器上的NP中，并且S-BSS机器上的每种NP语言都是R^n通常的封闭套件的可数字结合。此外，我们确定在没有真实常数的S-BSS计算机上的布尔np上，np表征了存在复杂性类别的自然片段（一类问题的多项式时间可以还原为真实的真实存在理论），因此NP和Pspace之间存在。最后，我们应用结果来确定概率独立性逻辑的数据复杂性。
We introduce a novel variant of BSS machines called Separate Branching BSS machines (S-BSS in short) and develop a Fagin-type logical characterisation for languages decidable in non-deterministic polynomial time by S-BSS machines. We show that NP on S-BSS machines is strictly included in NP on BSS machines and that every NP language on S-BSS machines is a countable union of closed sets in the usual topology of R^n. Moreover, we establish that on Boolean inputs NP on S-BSS machines without real constants characterises a natural fragment of the complexity class existsR (a class of problems polynomial time reducible to the true existential theory of the reals) and hence lies between NP and PSPACE. Finally we apply our results to determine the data complexity of probabilistic independence logic.
