Descriptive complexity of real computation and probabilistic independence logic

Show full item record



Permalink

http://hdl.handle.net/10138/319065

Citation

Hannula , M , Kontinen , J , Bussche , J V D & Virtema , J 2020 , Descriptive complexity of real computation and probabilistic independence logic . in Proceedigs of the Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) . IEEE Computer Society , pp. 550–563 , Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , 08/07/2020 . https://doi.org/10.1145/3373718.3394773

Title: Descriptive complexity of real computation and probabilistic independence logic
Author: Hannula, Miika; Kontinen, Juha; Bussche, Jan Van den; Virtema, Jonni
Other contributor: University of Helsinki, Department of Mathematics and Statistics
University of Helsinki, Department of Mathematics and Statistics
University of Helsinki, Hokkaido University
Publisher: IEEE Computer Society
Date: 2020-07
Language: eng
Number of pages: 14
Belongs to series: Proceedigs of the Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
ISBN: 978-1-4503-7104-9
DOI: https://doi.org/10.1145/3373718.3394773
URI: http://hdl.handle.net/10138/319065
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 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.
Subject: cs.LO
cs.CC
math.LO
111 Mathematics
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
LICS_revision.pdf 579.7Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record