It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-one $C$-reductions.

What is the weakest many-one reduction (computable in class $C$) for which the class of P-complete problems remains unchanged?

Note that $C$ is contained in $P$.

  • 1
    $\begingroup$ I don't understand your intro. $\mathrm{P}$ is closed under polytime reductions so, for any $\mathrm{C}$, $\mathrm{C=P}$ implies that every [non-trivial] problem in $\mathrm{P}$ is $\mathrm{P}$-complete under $\mathrm{C}$-reductions. $\endgroup$ Jun 1, 2019 at 11:02

1 Answer 1


There is first-order reductions.

See Immerman's book, Chapter 3, Theorem 3.26 which states that $\mathrm{REACH}_a$ is complete for $\mathrm{P}$ via first-order reductions.

Also, see my question, for related information on $\mathrm{NP}$.

  • $\begingroup$ Note that Immerman assumes a rather rich first-order setting that can do bit arithmetic and so on. $\endgroup$ Sep 19, 2018 at 14:23
  • $\begingroup$ Yes, it seems that weak reduction for $\mathrm{P}$-completeness is more cumbersome. $\mathrm{FO}+\mathrm{BIT}$ is known to capture uniform-$\mathrm{ACC}^0$, which in turn, has not yet been separated from $\mathrm{NC}^1$. See Lautemann et al.. $\endgroup$ Sep 19, 2018 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.