Descriptive complexity of real computation and probabilistic independence logic

Miika Hannula, Juha Kontinen, Jan Van den Bussche, Jonni Virtema

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.
Alkuperäiskielienglanti
OtsikkoProceedigs of the Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Sivumäärä14
KustantajaIEEE Computer Society
Julkaisupäiväheinäkuuta 2020
Sivut 550–563
ISBN (painettu)978-1-4503-7104-9
DOI - pysyväislinkit
TilaJulkaistu - heinäkuuta 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaThirty-Fifth Annual ACM/IEEE Symposium on
Logic in Computer Science (LICS)
-
Kesto: 8 heinäkuuta 202011 heinäkuuta 2020
http://lics.siglog.org/lics20/

Tieteenalat

  • 111 Matematiikka

Siteeraa tätä