The complexity of definability by open first-order formulas

DOI10.1093/JIGPAL/JZAA008MaRDI QIDQ3386916zbMATH OpenOpenAlexFDO

Authors Carlos Areces, Daniel Penazzi, Pablo Ventura, Miguel Campercholi

Publication date 8 January 2021

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.04637

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07) Parameterized complexity, tractability and kernelization (68Q27)

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 $mathbfmathcalL$, the $mathbfmathcalL$-Definability Problem for finite structures takes as input a finite structure $mathbfA$ and a target relation $T$ over the domain of $mathbfA$, and determines whether there is a formula of $mathbfmathcalL$ whose interpretation in $mathbfA$ 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 $mathrmcoW[1]$-complete for every vocabulary $au$ with at least one, at least binary, relation.

Recommendations

• The Exact Complexity of the First-Order Logic Definability Problem
• Complexity of the first-order theory of almost all finite structures
• scientific article; zbMATH DE number 4150340
• New Computational Paradigms
• scientific article; zbMATH DE number 4014674
• Generic complexity of first-order theories
• scientific article; zbMATH DE number 4189692
• Complexity of deciding the first-order theory of real closed fields
• First-order definability on finite structures
• scientific article; zbMATH DE number 4200184

Cited in

(4)

• The Exact Complexity of the First-Order Logic Definability Problem
• Deciding quantifier-free definability in finite algebraic structures
• scientific article; zbMATH DE number 4029504 (Why is no real title available?)
• Deciding open definability via subisomorphisms

This page was built for publication: The complexity of definability by open first-order formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386916)