The invariant problem for binary string structures and the parallel complexity theory of queries

摘要

We define the isomorphism and canonical invariant problems as queries on finite structures, and show that they are first-order definable on binary string structures that include the bit predicate. Applying our results to the parallel complexity theory of queries, we prove a unique correspondence between complexity-derived query classes and parallel complexity classes closed under constant parallel time reducibility. This directly extends a similar theorem of Chandra and Harel originally proved for sequential complexity classes closed under logarithmic space reducibility.