DIMACS TR: 93-20

A First-Order Isomorphism Theorem



Authors: Eric Allender, Jose Balcazar, and Neil Immerman

ABSTRACT

We show that for most complexity classes of interest, all sets complete under first-order projections are isomorphic under first-order isomorphisms. That is, a very restricted version of the Berman-Hartmanis Conjecture holds.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-20.ps
DIMACS Home Page