2026-07-22T16:55:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18550 2024-03-06T11:02:05Z ddc:004 open_access

Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification Balun, Jiří Masopust, Tomáš Osička, Petr Finite automata opacity fine-grained complexity Opacity is a property of privacy and security applications asking whether, given a system model, a passive intruder that makes online observations of system’s behaviour can ascertain some "secret" information of the system. Deciding opacity is a PSpace-complete problem, and hence there are no polynomial-time algorithms to verify opacity under the assumption that PSpace differs from PTime. This assumption, however, gives rise to a question whether the existing exponential-time algorithms are the best possible or whether there are faster, sub-exponential-time algorithms. We show that under the (Strong) Exponential Time Hypothesis, there are no algorithms that would be significantly faster than the existing algorithms. As a by-product, we obtained a new conditional lower bound on the time complexity of deciding universality (and therefore also inclusion and equivalence) for nondeterministic finite automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jiří Balun and Tomáš Masopust and Petr Osička 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.16 urn:nbn:de:0030-drops-185504 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode