The Big-O Problem

Chistikov, Dmitry, Kiefer, Stefan, Murawski, Andrzej S and Purser, David ORCID: 0000-0003-0394-1634 (2022) The Big-O Problem. Logical Methods in Computer Science, Volume.

PDF main.pdf - Author Accepted Manuscript Download (978kB) | Preview

Abstract

<jats:p>Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second. We show that the problem is undecidable, even for the instantiation of weighted automata as labelled Markov chains. Moreover, even when it is known that one weighted automaton is big-O of another, the problem of finding or approximating the associated constant is also undecidable. Our positive results show that the big-O problem is polynomial-time solvable for unambiguous automata, coNP-complete for unlabelled weighted automata (i.e., when the alphabet is a single character) and decidable, subject to Schanuel's conjecture, when the language is bounded (i.e., a subset of $w_1^*\dots w_m^*$ for some finite words $w_1,\dots,w_m$) or when the automaton has finite ambiguity. On labelled Markov chains, the problem can be restated as a ratio total variation distance, which, instead of finding the maximum difference between the probabilities of any two events, finds the maximum ratio between the probabilities of any two events. The problem is related to $\varepsilon$-differential privacy, for which the optimal constant of the big-O notation is exactly $\exp(\varepsilon)$.</jats:p>

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	29 Mar 2023 09:50
Last Modified:	17 Mar 2024 16:03
DOI:	10.46298/lmcs-18(1:40)2022
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3169339