The complexity of definability by open first-order formulas

DOI10.1093/JIGPAL/JZAA008zbMATH Open1497.68220arXiv1904.04637OpenAlexW3028958672MaRDI QIDQ3386916FDOQ3386916

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)

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.

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

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

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)

Cited In (4)

• The Exact Complexity of the First-Order Logic Definability Problem
• Deciding quantifier-free definability in finite algebraic structures
• Title not available (Why is that?)
• 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)