Paper Info
Title
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 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.
Year
DOI
Venue
2020
10.1145/3373718.3394773
LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science Saarbrücken Germany July, 2020
Keywords
DocType
ISSN
Blum-Shub-Smale machines, descriptive complexity, team semantics, independence logic, real arithmetic
Conference
1043-6871
ISBN
Citations 
PageRank 
978-1-4503-7104-9
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Miika Hannula16610.10
Juha Kontinen217624.67
Jan Van den Bussche31859602.40
Jonni Virtema47911.93