Descriptive complexity of real computation and probabilistic independence logic

Abstract

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 R n. Moreover, we establish that on Boolean inputs NP on S-BSS machines without real constants char-acterises a natural fragment of the complexity class ∃R (a class of problems polynomial time reducible to the true ex-istential 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. CCS Concepts: • Theory of computation → Complexity theory and logic; Finite Model Theory; Models of computation; • Mathematics of computing → Probability and statistics.