The Complexity of Definability by Open First-Order Formulas

ARECES, CARLOS; CAMPERCHOLI, MIGUEL; PENAZZI, DANIEL; VENTURA, PABLO

LOGIC JOURNAL OF THE IGPL (PRINT)

OXFORD UNIV PRESS

Lugar: Oxford; Año: 2019 vol. 28 p. 1093 - 1105

1367-0751

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 afinite 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 coincideswith T. We show that the complexity of this problem for open first-order formulas (open definability, for short) is coNP-complete. We alsoinvestigate the parametric complexity of the problem, and prove that if the size and the arity of the target relation T are taken as parameters,thenopen definability is coW[1]-complete for every vocabulary τ with at least one, at least binary, relation.