Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/33433
Title: | Descriptive complexity of real computation and probabilistic independence logic | Authors: | Hannula, Miika Kontinen, Juha VAN DEN BUSSCHE, Jan VIRTEMA, Jonni |
Issue Date: | 2020 | Source: | LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, p. 550 -563 | 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. | Keywords: | Blum-Shub-Smale machines;descriptive complex- ity;team semantics;independence logic;real arithmetic | Document URI: | http://hdl.handle.net/1942/33433 | ISBN: | 978-1-4503-7104-9 | DOI: | 10.1145/3373718.3394773 | ISI #: | 000665014900043 | Rights: | © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2022 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
3373718.3394773.pdf Restricted Access | Published version | 722.34 kB | Adobe PDF | View/Open Request a copy |
2003.00644.pdf | Peer-reviewed author version | 324.82 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
10
checked on Oct 14, 2024
Page view(s)
22
checked on Jul 6, 2022
Download(s)
6
checked on Jul 6, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.