In [1], Agrawal proved the following:
For any complexity class $\mathcal{C}$ closed under $NC^1$ reductions, problems complete for $\mathcal{C}$ under $FO$ reductions are isomorphic via an isomorphism computable in $FO$.
This is a derandomized construction of a non-uniform $AC^0$ isomorphism theorem due to Allender, Agrawal & Rudich [2].
I am curious if any work has been done regarding isomorphism with respect to $AC^0[\oplus]$ reductions.
The only strategy we have to construct an isomorphism (that I've seen) essentially employs a resource-bounded Schroder-Bernstein argument, which requires that completeness of a problem $A$ for $\mathcal{C}$ under, say, $r$ reductions (where $r$ is a complexity measure) implies completeness of $A$ for $\mathcal{C}$ under 1-1, length-increasing, invertible $r$ reductions. So I'd be specifically interested in results of the following form:
$A$ is $\leq_m^{AC^0[\oplus]}$-complete for $\mathcal{C}$ $\implies$ $A$ is $\leq_{P}^{AC^0[\oplus]}$-complete for $\mathcal{C}$ where property $P$ is some combination of $\{$1-1, invertible, length-increasing$\}$
Sources:
- Manindra Agrawal, The First-Order Isomorphism Theorem. FSTTCS 2001, LNCS 2245: 70-82.
- Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. JCSS 57: 127-143, 1999.
