The complexity of definability by open first-order formulas

C. Areces, M. Campercholi, D. Penazzi, and P. Ventura. The complexity of definability by open first-order formulas. Logic Journal of the IGPL, 28(6):1093–1105, 2020.

Download

[pdf] 

Abstract

In this article we formally define and investigate the computational complexity of the Definability Problem for open first-order formulas (i.e., quantifier free first-order formulas) with equality. Given a logic L, the L-Definability Problem for finite structures takes as input a finite structure A and a target relation T over the domain of A, and determines whether there is a formula of L whose interpretation in A coincides with T . We show that the complexity of this problem for open first-order formulas (open definability, for short) is coNP- complete. We also investigate the parametric complexity of the prob- lem, and prove that if the size and the arity of the target relation T are taken as parameters then open definability is coW[1]-complete for every vocabulary Ï„ with at least one, at least binary, relation.

BibTeX

@Article{ArecesCPV20,
  author =       "C. Areces and M. Campercholi and D. Penazzi and P.
                 Ventura",
  journal =      "Logic Journal of the {IGPL}",
  ISSN =         "1367--0751",
  title =        "The complexity of definability by open first-order
                 formulas",
  year =         "2020",
  number =       "6",
  abstract =     "In this article we formally define and investigate the
                 computational complexity of the Definability Problem
                 for open first-order formulas (i.e., quantifier free
                 first-order formulas) with equality. Given a logic L,
                 the L-Definability Problem for finite structures takes
                 as input a finite structure A and a target relation T
                 over the domain of A, and determines whether there is a
                 formula of L whose interpretation in A coincides with T
                 . We show that the complexity of this problem for open
                 first-order formulas (open definability, for short) is
                 coNP- complete. We also investigate the parametric
                 complexity of the prob- lem, and prove that if the size
                 and the arity of the target relation T are taken as
                 parameters then open definability is coW[1]-complete
                 for every vocabulary Ï„ with at least one, at least
                 binary, relation.",
  pages =        "1093--1105",
  volume =       "28",
  bibsource =    "dblp computer science bibliography, https://dblp.org",
  biburl =       "https://dblp.org/rec/journals/igpl/ArecesCPV20.bib",
  doi =          "10.1093/jigpal/jzaa008",
  timestamp =    "Wed, 29 Sep 2021 17:30:52 +0200",
  URL =          "https://doi.org/10.1093/jigpal/jzaa008",
}