6
$\begingroup$

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$.

$\endgroup$
  • $\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$ – David Richerby Jun 1 at 11:02
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note that Immerman assumes a rather rich first-order setting that can do bit arithmetic and so on. $\endgroup$ – David Richerby Sep 19 '18 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$ – Thinh D. Nguyen Sep 19 '18 at 14:38

Your Answer

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

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