A FIRST-ORDER ISOMORPHISM THEOREM

Authors
ALLENDER E BALCAZAR J IMMERMAN N
Citation
E. Allender et al., A FIRST-ORDER ISOMORPHISM THEOREM, SIAM journal on computing, 26(2), 1997, pp. 557-567
Citations number
37
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
26
Issue
2
Year of publication
1997
Pages
557 - 567
Database
ISI
SICI code
0097-5397(1997)26:2<557:AFIT>2.0.ZU;2-K
Abstract
We show that for most complexity classes of interest, all sets complet e under first-order projections (fops) are isomorphic under first-orde r isomorphisms. That is, a very restricted version of the Berman-Hartm anis conjecture holds. Since ''natural'' complete problems seem to sta y complete via fops, this indicates that up to first-order isomorphism there is only one ''natural'' complete problem for each ''nice'' comp lexity class.