93-20 A First-Order Isomorphism Theorem

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