Allender, Eric; Balcázar, José; Immerman, Neil A first-order isomorphism theorem. (English) Zbl 0874.68124 SIAM J. Comput. 26, No. 2, 557-567 (1997). Summary: We show that for most complexity classes of interest, all sets complete under first-order projections (fops) are isomorphic under first-order isomorphisms. That is, a very restricted version of the Berman-Hartmanis conjecture holds. Since ”natural” complete problems seem to stay complete via fops, this indicates that up to first-order isomorphism there is only one ”natural” complete problem for each ”nice” complexity class. Cited in 7 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 03D15 Complexity of computation (including implicit computational complexity) Keywords:complexity classes; descriptive complexity; reduction; first-order projection PDFBibTeX XMLCite \textit{E. Allender} et al., SIAM J. Comput. 26, No. 2, 557--567 (1997; Zbl 0874.68124) Full Text: DOI