06113538

j

06113538 Bova, Simone Chen, Hubie Valeriote, Matthew On the expression complexity of equivalence and isomorphism of primitive positive formulas. Theory Comput. Syst. 50, No. 2, 329-353 (2012). 2012 Springer-Verlag, New York, NY EN primitive positive formulas equivalence isomorphism computational complexity clones

doi:10.1007/s00224-010-9302-7

Summary: 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.