  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
$\mathbf{\mathcal{L}}$, the $\mathbf{\mathcal{L}}$-Definability Problem for
finite structures takes as input a finite structure $\mathbf{A}$ and a target
relation $T$ over the domain of $\mathbf{A}$, and determines whether there is a
formula of $\mathbf{\mathcal{L}}$ whose interpretation in $\mathbf{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 $\mathrm{coW}[1]$-complete for every vocabulary $\tau$ with at
least one, at least binary, relation.
