The complexity of definability by open first-order formulas

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 an 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 problem 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.