Homogeneity and Homogenizability: Hard Problems for the Logic SNP

Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Theory of numerations, effectively presented structures (03D45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We show that the question whether a given SNP sentence defines a homogenizable class of finite structures is undecidable, even if the sentence comes from the connected Datalog fragment and uses at most binary relation symbols. As a byproduct of our proof, we also get the undecidability of some other properties for Datalog programs, e.g., whether they can be rewritten in MMSNP, whether they solve some finite-domain CSP, or whether they define the age of a reduct of a homogeneous Ramsey structure in a finite relational signature. We subsequently show that the closely related problem of testing the amalgamation property for finitely bounded classes is EXPSPACE-hard or PSPACE-hard, depending on whether the input is specified by a universal sentence or a set of forbidden substructures.

This page was built for publication: Homogeneity and Homogenizability: Hard Problems for the Logic SNP

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