一句话：引入分离分支 BSS 机，给出其 NP 的 Fagin 型逻辑刻画，并用于概率独立性逻辑的数据复杂性。
本文研究实数计算模型 BSS 机上的描述复杂性。作者提出分离分支 BSS 机（S-BSS），建立 Fagin 型逻辑刻画，刻划其非确定性多项式时间可判定语言。结果表明 S-BSS 上的 NP 严格包含于 BSS 上的 NP，且每个 S-BSS NP 语言是 R^n 中闭集的可数不交并。进一步，在布尔输入且无实数常数的情形，S-BSS NP 刻画 ∃R 的一个自然片段，因而位于 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 nondeterministic 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 disjoint union of closed sets in the usual topology of Rn. Moreover, we establish that on Boolean inputs NP on S-BSS machines without real constants characterises a natural fragment of the complexity class ∃R (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.
@inproceedings{paperbot5526,
title = {Descriptive complexity of real computation and probabilistic independence logic},
author = {Miika Hannula and Juha Kontinen and Jan Van den Bussche and Jonni Virtema},
booktitle = {LICS},
year = {2020},
doi = {10.1145/3373718.3394773}
}