Sign in
Back
A first-order isomorphism theorem
Book chapter   Peer reviewed

A first-order isomorphism theorem

Eric Allender, Jose Balcázar and Neil Immerman
STACS 93, pp.163-174
Lecture Notes in Computer Science, Springer Berlin Heidelberg
05/27/2005
DOI: https://doi.org/10.1007/3-540-56503-5_19

Abstract

Boolean Variable Binary String Closed Term Constant Symbol Isomorphism Conjecture
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.

Metrics

7 Record Views

Details