×

A first-order isomorphism theorem. (English) Zbl 0874.68124

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.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI