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$\}$


  1. Manindra Agrawal, The First-Order Isomorphism Theorem. FSTTCS 2001, LNCS 2245: 70-82.
  2. Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. JCSS 57: 127-143, 1999.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.