SIAM Journal on Computing · 1987 · 545 citations · 20 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationTranslation TheoryComputational ComplexityComputational Complexity ClassesFirst-order LogicModel TheoryPredicate LogicStructural ComplexityCapture Of Complexity ClassesComplete ProblemsCompleteness ResultsComplexityComplexity ClassesComplexity-theoretic ReductionsProjectionsReductions
We present a series of operators of apparently increasing power which when added to first-order logic produce a series of languages in which exactly the properties checkable in a certain complexity class may be expressed. We thus give alternate characterizations of most important complexity classes. We also introduce reductions appropriate for our setting: first-order translations, and a restricted, quantifier free version of these called projection translations. We show that projection translations are a uniform version of Valiant’s projections, and that the usual complete problems remain complete via these very restrictive reductions.
20
Larry J. Stockmeyer · Theoretical Computer Science · 1976 · 1.3K citations
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer · Journal of the ACM · 1981 · 1.2K citations · Full text
Random walks, universal traversal sequences, and the complexity of maze problems
Romas Aleliunas, Richard M. Karp, Richard J. Lipton et al. · 1979 · 705 citations
Universality of data retrieval languages
Alfred V. Aho, Jeffrey D. Ullman · 1979 · 634 citations · Full text
Computing, Computer Science, Algebra +14
∑11-Formulae on finite structures
Miklós Ajtai · Annals of Pure and Applied Logic · 1983 · 586 citations