On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas
MATTHEW A. VALERIOTE, Simone Bova, Hubie Chen · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2010
We study the complexity of equivalence and isomorphism on primitive positive formulas with respect to a given structure. We study these problems for various fixed structures; we present generic hardness and complexity class containment results, and give classification theorems for the case of two-element (boolean) structures.