The First-order isomorphism theorem

Agrawal, Manindra (2001) The First-order isomorphism theorem Lecture Notes in Computer Science, 2245 . pp. 70-82. ISSN 0302-9743

PDF - Author Version

Official URL:

Related URL:


For any class C und closed under NC1 reductions, it is shown that all sets complete for C under first-order (equivalently, Dlogtimeuniform AC0) reductions are isomorphic under first-order computable isomorphisms.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:92024
Deposited On:26 May 2012 13:52
Last Modified:19 May 2016 05:36

Repository Staff Only: item control page