# What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?

It is common to define $P$-completeness with respect to log-space many-one reductions.

I am looking for a complexity class $C \subseteq \mathsf{L}$ such that there are $\mathsf{P}$-complete problems w.r.t. many-one $C$-reductions.

What is the smallest known many-one reduction class $C$ such that HornSAT is complete for $\mathsf{P}$ under $C$-reductions?

The question was originally posted on CS with no answer.

• Maybe you mean all non-trivial problems: the empty language and the language whose complement is empty cannot be complete. – Sasho Nikolov Jul 29 '15 at 13:58
• @SashoNikolov Sure, I am not interested in trivial languages! – Mohammad Al-Turkistany Jul 29 '15 at 14:28
• I don't understand the question. If C=P then all problems in P except the trivial ones are complete for P under C-reductions, and this is the case independent of what C is. – Kaveh Jul 29 '15 at 15:30
• @Kaveh What is the smallest such class $C$? For instance, is HornSAT complete for $P$ under $NC^1$ Reductions? – Mohammad Al-Turkistany Jul 29 '15 at 15:47
• I share Kaveh’s confusion about the first paragraph. But concerning the blue question, a reasonable encoding of Horn-SAT is P-complete under DLOGTIME reductions. – Emil Jeřábek Jul 29 '15 at 17:09

It is easy to show that the Circuit Value Problem is complete for $\mathsf{P}$ under $\mathsf{AC^0}$ reductions (see András's comment below).
For an easier example consider $$A = \{\langle M,x,y\rangle \mid \text{M accepts x in |y| steps} \}$$
If a class of reductions $C$ contains constant functions, pairing of strings, and functions where the size of their output can bound any polynomial; then $A$ is complete for $\mathsf{P}$ w.r.t. $C$.