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

*(English)*Zbl 0766.68043Summary: 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 A.Chandra and D. Harel [J. Comput. Syst. Sci. 25, 99-128 (1982; Zbl 0511.68073)] originally proved for sequential complexity classes closed under logarithmic space reducibility.

##### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q25 | Analysis of algorithms and problem complexity |

68P15 | Database theory |

##### Keywords:

structure and complexity of database queries; parallel complexity theory of queries; constant parallel time reducibility
PDF
BibTeX
XML
Cite

\textit{S. Lindell}, J. Comput. Syst. Sci. 44, No. 3, 385--410 (1992; Zbl 0766.68043)

Full Text:
DOI

##### References:

[1] | \scD. A. M. Barrington, N. Immerman, and H. Straubing, “On Uniformity within NC^1,” revised version, University of Massachusetts COINS Technical Report 89-88 · Zbl 0719.68023 |

[2] | Buss, S.R., The Boolean formula value problem is in ALOGTIME, (), 123-131 |

[3] | Chandra, A.; Harel, D., Structure and complexity of relational queries, J. comput. system sci., 25, No. 1, 99-128, (1982) · Zbl 0511.68073 |

[4] | Chandra, A.; Stockmeyer, L.; Vishkin, U., Constant depth reducibility, SIAM J. compul., 13, No. 2, 423-429, (1984) · Zbl 0538.68038 |

[5] | Denenberg, L.; Gurevich, Y.; Shelah, S., Definability by constant-depth polynomial-size circuits, Inform. and control, 70, 216-240, (1986) · Zbl 0629.94023 |

[6] | Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. math., 49, 129-141, (1961) · Zbl 0096.24303 |

[7] | Fagin, R., Generalized first-order spectra and polynomial time recognizable sets, (), 43-73 |

[8] | Fraïssé, R., Sur LES classifications des systems de relations, Publ. sci. univ. alger, I, (1954) |

[9] | Furst, M.; Saxe, J.B.; Sipser, M., Parity, circuits, and the polynomial-time hierarchy, Math. systems theory, 17, 13-27, (1984) · Zbl 0534.94008 |

[10] | Garey, M.R.; Johnson, D.S., Computers and intractability—A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039 |

[11] | Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701 |

[12] | Immerman, N., Expressibility and parallel complexity, SIAM J. comput., 18, No. 3, 625-638, (1989) · Zbl 0688.68038 |

[13] | \scN. Immerman, Expressibility as a complexity measure: Results and directions, in “Proceedings of the second Annual Conference of Structure in Complexity Theory”, pp. 194-202 (a broader survey without proofs) |

[14] | Immerman, N., Descriptive and computational complexity, (), 75-91, (a narrower survey with proofs) |

[15] | Immerman, N., Relational queries computable in polynomial time, Inform. and control, 68, 86-104, (1986) · Zbl 0612.68086 |

[16] | Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 760-778, (1987) · Zbl 0634.68034 |

[17] | Immerman, N., Nondeterministic space is closed under complementation, SIAM J. comput., 17, No. 5, 935-938, (1988) · Zbl 0668.68056 |

[18] | \scN. Immerman and S. Landau, The complexity of iterated multiplication, in “Proceedings of the 4th Annual IEEE Conference on Structure in Complexity Theory,” pp. 104-111. · Zbl 0818.68076 |

[19] | Karp, R.M., Probabilistic analysis of a canonical numbering algorithm for graphs, (), 365-378 |

[20] | Lindell, S., The logical complexity of queries on unordered graphs, () |

[21] | Lindell, S., A logspace algorithm for tree canonization, (1991), preprint manuscript |

[22] | Read, R.C.; Corneil, D.G., The graph isomorphism disease, J. graph theory, 1, 339-363, (1977) · Zbl 0381.05026 |

[23] | Stockmeyer, L., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1-22, (1977) · Zbl 0353.02024 |

[24] | Stockmeyer, L.; Vishkin, U., Simulation of parallel random access machines by circuits, SIAM J. comput., 13, No. 2, 409-422, (1984) · Zbl 0533.68048 |

[25] | Vardi, M.Y., Complexity of relational query languages, (), 137-146 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.