Complexity of Existential Positive First-Order Logic

2010/11/22 by Manuel Bodirsky, Bodirsky, Manuel, Miki Hermann +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1011.4757

openalex publication_date 2010/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logspace or complete for the class CSP(gamma)_NP under deterministic polynomial-time many-one reductions. Here, CSP(gamma)_NP is the class of problems that can be reduced to the Constraint Satisfaction Problem of gamma under non-deterministic polynomial-time many-one reductions.

Related

• On the Complexity of Existential Positive Queries
• The complexity of positive first-order logic without equality
• The complexity of positive first-order logic without equality II: The four-element case
• Counting Answers to Existential Positive Queries: A Complexity Classification
• Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three